Cod sursa(job #991638)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 31 august 2013 02:53:16
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.98 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "atac";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;


vector<vector<pair<int, int> > > G;

int N, M, P;
int X, Y, A, B, C, D;
int MaxHeight = 0;

vector<int> level;
vector<int> parent;

vector<int> parentCost;

vector<int> lg;
vector<vector<int> > dpParent;
vector<vector<int> > dpCost;

vector<int> eulerPath;
vector<int> minIndex;

vector<vector<int> > rmq;

void Euler(int x, int l)
{
	eulerPath.push_back(x);

	if(minIndex[x] == 0)
	{
		level[x] = l;
		MaxHeight = max(MaxHeight, level[x]);
		minIndex[x] = eulerPath.size() - 1;	
	}

	for(vector<pair<int, int> >::iterator itr = G[x].begin();
		itr != G[x].end();
		itr++)
	{
		if(parent[x] != itr->first)
		{
			parentCost[itr->first] = itr->second;
			parent[itr->first] = x;
			Euler(itr->first, l + 1);
			eulerPath.push_back(x);
		}
	}
}

inline int QueryRmq(int x, int y)
{
	x = minIndex[x];
	y = minIndex[y];
	if(x > y) swap(x, y);

	int len = y - x + 1;
	int c = lg[len];
	int dif = len - (1 << c);

	int min1 = rmq[c][x];
	int min2 = rmq[c][x + dif];
	return level[min1] < level[min2] ? min1 : min2;
}


inline int QueryMinToParent(int x, int y)
{
	int pLevel = level[y];
	int cLevel = level[x];
	int difLevel = cLevel - pLevel;

	int mini = INF;
	int c = x;

	for(int i = lg[difLevel]; i >= 0; i--)
	{
		if(level[dpParent[i][c]] >= pLevel)
		{
			mini = min(mini, dpCost[i][c]);
			c = dpParent[i][c];
			if(c == y) break;
		}
	}

	return mini;
}

inline int QueryMin(int x, int y)
{
	int lca = QueryRmq(x, y);

	return min(QueryMinToParent(x, lca), QueryMinToParent(y, lca));
}





int main()
{
	fstream fin(infile.c_str(), ios::in);

	fin >> N >> M >> P;

	G.resize(N + 1);
	level.resize(N + 1);
	parent.resize(N + 1);
	parentCost.resize(N + 1);
	minIndex.resize(N + 1);

	for(int i = 2; i <= N; i++)
	{
		int x, y;
		fin >> x >> y;

		G[i].push_back(make_pair(x, y));
		G[x].push_back(make_pair(i, y));

	}

	fin >> X >> Y;
	fin >> A >> B >> C >> D;


	
	Euler(1, 1);


	lg.resize(max(MaxHeight, (int)eulerPath.size()) + 1);
	lg[2] = 1;

	for(unsigned i = 3; i < lg.size(); i++)
	{
		lg[i] = lg[i/2] + 1;
	}

	dpParent.resize(lg[MaxHeight] + 1, vector<int>(N + 1));
	dpCost.resize(lg[MaxHeight] + 1, vector<int>(N + 1));

	for(int i = 1; i <= N; i++)
	{
		dpParent[0][i] = parent[i];
		dpCost[0][i] = parentCost[i];
	}

	for(int i = 1; i <= lg[MaxHeight]; i++)
	{
		for(int j = 1; j <= N; j++)
		{
			dpParent[i][j] = dpParent[i - 1][dpParent[i-1][j]];
			dpCost[i][j] = min(dpCost[i-1][j], dpCost[i-1][dpParent[i-1][j]]);
		}
	}

	rmq.resize(lg[eulerPath.size()] + 1);
	rmq[0].resize( eulerPath.size());

	for(unsigned i = 0; i < eulerPath.size(); i++)
	{
		rmq[0][i] = eulerPath[i];
	}

	for(int i = 1; i <= lg[eulerPath.size()]; i++)
	{
		rmq[i].resize(eulerPath.size() - (1 << i) + 1);
		for(unsigned j = 0; j <= eulerPath.size() - (1 << i); j++)
		{
			int min1 = level[rmq[i-1][j]];
			int min2 = level[rmq[i-1][j + (1 << (i - 1))]];

			rmq[i][j] = min1 < min2 ? rmq[i-1][j] : rmq[i-1][j + (1 << (i -1 ))];

		}
	}

	fin.close();

	fstream fout(outfile.c_str(), ios::out);

	for(int i = 0; i < M; i++)
	{
		int Z = QueryMin(X, Y);
		int newX = ((X * A + Y * B) % N) + 1;
		int newY = ((Y * C + Z * D) % N) + 1;

		X = newX;
		Y = newY;
		if(M - P  <= i)
		{
			fout << Z << "\n";
		}
	}


	fout.close();
}