Cod sursa(job #592850)

Utilizator andra23Laura Draghici andra23 Data 30 mai 2011 22:11:24
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.23 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 32005, logmaxn = 15, sqrtmaxn = 600, maxbombs = 100005;
int t[maxn], level[maxn], l[maxn], bombs[maxn], viz[maxn];
vector < pair <int,int> > v[maxn];
int c[maxn][logmaxn];
vector <int> longPath[maxn];
int longPathSon[maxn], whatPath[maxn], whatPos[maxn], pathParent[maxn];
vector <int> trees[maxn];
ofstream g("atac.out");

void calculateLog(int n) {
	l[1] = 0;
	int next = 2;
	for (int i = 2; i <= n; i++) {
		l[i] = l[i-1];
		if (i == next) {
			l[i]++;
			next = next*2;	
		}	
	}	
}

void findLevel(int nod) {
	viz[nod] = 1;
	for (int i = 0; i < v[nod].size(); i++) {
		int son = v[nod][i].first;
		int bomb = v[nod][i].second;
		if (viz[son] == 0) {
			t[son] = nod;
			level[son] = level[nod]+1;
			bombs[son] = bomb;
			findLevel(son);
		}
	}
}

int findLongest(int nod) {
	int max = 0, maxSon = -1;
	for (int i = 0; i < v[nod].size(); i++) {
		int son = v[nod][i].first;
		if (level[son] > level[nod]) {
			int x = findLongest(son);
			if (x > max) {
				max = x;
				maxSon = son;
			}				
		}	
	}
	longPathSon[nod] = maxSon; 
	return max+1;	
}

void decomposeLong(int nod, int &path) {
	longPath[path].push_back(nod);
	whatPath[nod] = path;
	whatPos[nod] = longPath[path].size()-1;
	if (longPathSon[nod] != -1)
		decomposeLong(longPathSon[nod], path);
	
	for (int i = 0; i < v[nod].size(); i++) {
		int son = v[nod][i].first;
		if (level[son] > level[nod] && son != longPathSon[nod]) { 
			path++;
			pathParent[path] = nod;
			decomposeLong(son, path);
		}
	}
}

void preprocess(int n) {
	for (int i = 1; i <= n; i++)
		for (int j = 0; (1<<j) <= n; j++) 
			c[i][j] = -1;
	
	for (int i = 1; i <= n; i++)
		c[i][0] = t[i];
		
	for (int j = 1; (1<<j) <= n; j++)
		for (int i = 1; i <= n; i++) 
			if (c[i][j-1] != -1)
				c[i][j] = c[c[i][j-1]][j-1];
}

int findAncestor (int x, int ancestorLevel) {
	int logx = l[level[x]];
	for (int i = logx; i >= 0; i--) 
		if (c[x][i] != -1 && level[c[x][i]] >= ancestorLevel)
			x = c[x][i];	
			
	return x;
}

int lca(int x, int y) {
	if (level[x] < level[y]) {	
		int aux = x;
		x = y;
		y = aux;	
	}
	
	int logx = l[level[x]];
	for (int i = logx; i >= 0; i--)
		if (c[x][i] != -1 && level[c[x][i]] >= level[y])
			x = c[x][i];
			
	if (x == y)
		return x;
		
	for (int i = logx; i >= 0; i--)
		if (c[x][i] != -1 && c[x][i] != c[y][i]) {
			x = c[x][i];
			y = c[y][i];	
		}
	return t[x];
}

void buildSegmentTree(int tree, vector <int> &path, int nod, int left, int right) {
	if (left == right) {
		trees[tree][nod] = bombs[path[left]];	
		return;
	}
	
	int m = (left+right)/2;
	buildSegmentTree(tree, path, 2*nod, left, m);
	buildSegmentTree(tree, path, 2*nod+1, m+1, right);
	
	if (trees[tree][2*nod] < trees[tree][2*nod+1])
		trees[tree][nod] = trees[tree][2*nod];
	else 
		trees[tree][nod] = trees[tree][2*nod+1];
}

int queryST(int tree, int nod, int left, int right, int a, int b) {
	if (a <= left && right <= b) 
		return trees[tree][nod];
		
	int m = (left+right)/2;
	int minim = maxbombs, x;
	if (a <= m)
		minim = queryST(tree, 2*nod, left, m, a, b);
		
	if (m+1 <= b) {
		x = queryST(tree, 2*nod+1, m+1, right, a, b);
		if (x < minim)
			minim = x;
	}
	return minim;
}

int pathMinimum(int u, int v) {
	int minValue = maxbombs;
	int aux;
	while (true) {
		if (whatPath[u] == whatPath[v]) {
			aux = queryST(whatPath[u], 1, 0, longPath[whatPath[u]].size()-1, 
				whatPos[u], whatPos[v]);
			if (aux < minValue)
				minValue = aux; 
			break;	
		}	
		else {
			aux = queryST(whatPath[v], 1, 0, longPath[whatPath[v]].size()-1, 
				whatPos[1], whatPos[v]);
			if (aux < minValue)
				minValue = aux; 
			v = pathParent[whatPath[v]];
		}
	}
	return minValue;	
}

int query(int x, int y) {
	int w = lca(x, y);
	int upperX = findAncestor(x, level[w]+1);
	int upperY = findAncestor(y, level[w]+1);
	
	int minValue = maxbombs, min1, min2;
		if (x != w) {
			min1 = pathMinimum(upperX, x);
			if (minValue > min1)
				minValue = min1;
		}
		if (y != w) {
			min2 = pathMinimum(upperY, y);
			if (minValue > min2)
				minValue = min2;
		}
	return minValue;
}

int main() {
	ifstream f("atac.in");

	int n, m, p, x, y, a, b, cc, d;
	f >> n >> m >> p;
	
	t[1] = -1;
	bombs[1] = 0;
	
	for (int i = 2; i <= n; i++) {
		f >> a >> b;
		v[a].push_back(make_pair(i,b));
		v[i].push_back(make_pair(a,b));
	}
	
	level[1] = 1;
	findLevel(1);
	calculateLog(n);
	preprocess(n);
	
	findLongest(1);
	pathParent[1] = -1;
	int paths = 1;
	
	decomposeLong(1, paths);	
	//decomposeHeavy(1, paths);
	
	/*
	for (int i = 1; i <= paths; i++) {
		g << i << ": ";
		for (int j = 0; j < longPath[i].size(); j++)
			g << longPath[i][j] << " ";
		g << endl;	
	}
	*/
	
	for (int path = 1; path <= paths; path++) {
		trees[path] = vector<int>(4*longPath[path].size());
		buildSegmentTree(path, longPath[path], 1, 0, longPath[path].size()-1);
	}
	
	f >> x >> y >> a >> b >> cc >> d;
	int z;
	for (int i = 1; i <= m; i++) {
		if (x == y)
			z = 0;
		else 
			z = query(x, y);
		
		if (m-i+1 <= p)
			g << z << '\n';
		x = (a*x + b*y)%n + 1;
		y = (cc*y + d*z)%n + 1;
	}
	
	return 0;	
}