Cod sursa(job #62077)

Utilizator alextheroTandrau Alexandru alexthero Data 21 mai 2007 19:45:18
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <stdio.h>
#include <vector>

#define inf (int)1e8
#define nmax 32005
#define logmax 15
#define pb push_back

using namespace std;
typedef pair<int,int> ii;

char v[nmax];
ii str[nmax][logmax];
int a,b,c,d,x,y,z,nx,ny,n,m,p,i,j,n1,v1,niv[nmax];
vector <ii> e[nmax];

inline int max(int a,int b) {
	if(a > b) return a;
	else return b;
}

inline int min(int a,int b) {
	if(a > b) return b;
	else return a;
}

void dfs(int x,int lev) {
	v[x] = 1;
	niv[x] = lev;
	for(int i = 0; i < (int)e[x].size(); i++) 
		if(!v[e[x][i].first]) {
			int last,nod = e[x][i].first;
			str[nod][0] = ii(x,e[x][i].second);
			for(int j = 1; j < logmax; j++) {
				last = str[nod][j - 1].first;
				if(last == 0 || str[last][j  - 1].first == 0) break;
				str[nod][j] = ii(str[last][j - 1].first,min(str[nod][j - 1].second,str[last][j - 1].second));
			}
			dfs(nod,lev + 1);
		}
}

int query(int x,int y) {
	int rez = inf,aux = 0,last_lev = logmax - 1,lx = x,ly = y;
	if(x == y) return 0;
	if(niv[lx] > niv[ly]) {
		aux = lx;
		lx = ly;
		ly = aux;
	}

	while(niv[ly] > niv[lx]) {
		if(str[ly][last_lev].first == 0) last_lev--;
		else {
			if(niv[str[ly][last_lev].first] >= niv[lx]) {
				rez = min(rez,str[ly][last_lev].second);
				ly = str[ly][last_lev].first;
			}
			else last_lev--;
		}
	}

	last_lev = logmax - 1;
	while(lx != ly) {
		if(last_lev == 0 || str[lx][last_lev].first != str[ly][last_lev].second) {
			rez = min(rez,str[ly][last_lev].second);
			rez = min(rez,str[lx][last_lev].second);
			ly = str[ly][last_lev].first;
			lx = str[lx][last_lev].first;
		}
		else last_lev--;
	}

	return rez;
}

int main() {
	freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);

	scanf("%d%d%d",&n,&m,&p);
	for(i = 2; i <= n; i++) {
		scanf("%d%d",&n1,&v1);
		e[i].pb(ii(n1,v1));
		e[n1].pb(ii(i,v1));
	}

	dfs(1,1);

	scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);

	for(i = 1; i <= m; i++) {
		z = query(x,y);	
		nx = (x * a + y * b) % n + 1;
		ny = (y * c + z * d) % n + 1;
		if(i > m - p) printf("%d\n",z);
		x = nx; y = ny;
	}

	return 0;
}