Cod sursa(job #122161)

Utilizator andrei.12Andrei Parvu andrei.12 Data 11 ianuarie 2008 10:23:45
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define lg 100000
#define infinit 2000000000

using namespace std;

int n, m, p, i, u, vl, ind, x, nod, ad, p1, p2, pz[lg], aux, adl, lca, rz1, rz2, y, a, b, c, d, nr[lg], dst[lg], *v[lg], *w[lg], init[lg], pt[11], j;
struct sgtree{
	int st, dr, v, nod;
};
sgtree tre[10*lg];
struct ches{
	int nod, v;
};
ches q[3*lg], tt[lg], cnt[lg][11];
void euler(int nod, int ad){
	int i;
	
	q[++ind].nod = nod;
	q[ind].v = ad;
	pz[nod] = ind;
	for (i = 1; i <= nr[nod]; i ++){
		dst[v[nod][i]] += dst[nod] + w[nod][i];
		euler(v[nod][i], ad+1);
		q[++ind].nod = nod;
		q[ind].v = ad;
		pz[nod] = ind;
	}
}
void cstr(int st, int dr, int poz){
	int x;
	tre[poz].st = st;
	tre[poz].dr = dr;
	if (st == dr)
		init[st] = poz;
	else{
		x = (st+dr) / 2;
		cstr(st, x, 2*poz);
		cstr(x+1, dr, 2*poz+1);
	}
}
void query(int pz){
	if (tre[pz].st > p2 || tre[pz].dr < p1)
		return ;
	if (tre[pz].st >= p1 && p2 >= tre[pz].dr){
		if (tre[pz].v < adl){
			adl = tre[pz].v;
			lca = tre[pz].nod;
		}
	}
	else{
		if (tre[2*pz].st)
			query(2*pz);
		if (tre[2*pz+1].st)
			query(2*pz+1);
	}
}
int caut(int p, int nr){
	int rz = infinit;
	while (nr){
		int li = 0, ls = 10, gs, x;
		while (li <= ls){
			x = (li+ls) / 2;
			if (pt[x] <= nr){
				gs = x;
				li = x+1;
			}
			else
				ls = x-1;
		}
		nr = nr-pt[gs];
		if (cnt[p][gs].v < rz)
			rz = cnt[p][gs].v;
		p = cnt[p][gs].nod;
	}
	return rz;
}
int main()
{
	freopen("atac.in", "rt", stdin);
	freopen("atac.out", "wt", stdout);
	
	scanf("%d%d%d", &n, &m, &p);
	
	for (i = 2; i <= n; i ++){
		scanf("%d%d", &u, &vl);
		
		tt[i].nod = u;
		tt[i].v = vl;
		
		nr[u] ++;
		v[u] = (int*)realloc(v[u], (nr[u]+1)*sizeof(int));
		v[u][nr[u]] = i;
		w[u] = (int*)realloc(w[u], (nr[u]+1)*sizeof(int));
		w[u][nr[u]] = vl;
	}
	
	euler(1, 0);
	cstr(1, ind, 1);
	
	pt[0] = 1;
	for (i = 1; i <= 10; i ++)
		pt[i] = pt[i-1]*2;
	for (i = 1; i <= n; i ++)
		if (tt[i].nod){
			cnt[i][0].v = tt[i].v;
			cnt[i][0].nod = tt[i].nod;
		}
	for (i = 1; i <= 10; i ++)
		for (j = 1; j <= n; j ++){
			p1 = cnt[j][i-1].nod;
			if (cnt[j][i-1].v < cnt[p1][i-1].v)
				cnt[j][i].v = cnt[j][i-1].v, cnt[j][i].nod = cnt[j][i-1].nod;
			else
				cnt[j][i].v = cnt[p1][i-1].v, cnt[p1][i].nod = cnt[p1][i-1].nod;
		}
	
	for (i = 1; i <= ind; i ++){
		x = init[i];
		nod = q[i].nod;
		ad = q[i].v;
		
		while (x){
			if (!tre[x].nod){
				tre[x].nod = nod;
				tre[x].v = ad;
			}
			else
				if (ad < tre[x].v){
					tre[x].v = ad;
					tre[x].nod = nod;
				}
			x /= 2;
		}
	}
	
	scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
	
	for (i = 1; i <= m; i ++){
		p1 = pz[x];
		p2 = pz[y];
		
		if (p1 > p2)
			aux = p1, p1 = p2, p2 = aux;
		
		adl = infinit;
		lca = 0;
		query(1);
		
		//rz = dst[x] + dst[y] - 2*dst[lca];
		rz1 = caut(x, q[p1].v-adl);
		rz2 = caut(y, q[p2].v-adl);
		rz1 = min(rz1, rz2);
		
		x = (x*a + y*b) % n + 1;
		y = (y*c + rz1*d) % n + 1;
		
		if (m-i+1 <= p)
			printf("%d\n", rz1);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}