Cod sursa(job #587787)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 5 mai 2011 21:17:26
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 32010

int n, m, pp, t[20][nmax], cm[20][nmax], l[nmax], lm, e[nmax<<1], h, r[20][nmax<<1], f[nmax], lg[nmax<<1], lev[nmax<<1];
vector <pair<int, int> > g[nmax];

void df(int nod)
{
	int i, v;
	e[++h]=nod;
	lev[h]=l[nod];
	f[nod]=h;
	for (i=0; i<g[nod].size(); i++) 
	{
		v=g[nod][i].first;
		if (!l[v])
		{
			t[0][v]=nod;
			l[v]=l[nod]+1;
			cm[0][v]=g[nod][i].second;
			if (l[v]>lm) lm=l[v];
			df(v);
			e[++h]=nod;
			lev[h]=l[nod];
		}
	}
}

void rmq()
{
	int i, j;
	for (i=2; i<=h; i++) lg[i]=lg[i>>1]+1;
	for (i=1; i<=h; i++) r[0][i]=i;
	for (i=1; (1<<i)<h; i++)
		for (j=1; j<=h-(1<<i)+1; j++)
			if (lev[r[i-1][j]]<lev[r[i-1][j+(1<<(i-1))]])
				r[i][j]=r[i-1][j]; else
					r[i][j]=r[i-1][j+(1<<(i-1))];
}

int lca(int x, int y)
{
	x=f[x];
	y=f[y];
	if (x>y) swap(x, y);
	int d=lg[y-x+1];
	if (lev[r[d][x]]<lev[r[d][y-(1<<d)+1]])
		return e[r[d][x]]; else
			return e[r[d][y-(1<<d)+1]];
}

int search(int x, int y)
{
	if (x==y) return 1<<30;
	int i;
	for (i=0; (1<<i)<=lm && t[i][x]; i++)
	{
		if (l[t[i][x]]==l[y]) return cm[i][x]; else
		if (l[t[i][x]]<l[y]) return min(cm[i-1][x], search(t[i-1][x], y));
	}
	return min(cm[i-1][x], search(t[i-1][x], y));
}
	
int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	scanf("%d %d %d", &n, &m, &pp);
	int i, j, x, y, a, b, c, d, z, p;
	for (i=1; i<n; i++)
	{
		scanf("%d %d", &x, &y);
		g[x].push_back(make_pair(i+1, y));
		g[i+1].push_back(make_pair(x, y));
	}
	l[1]=1;
	df(1);
	for (i=1; (1<<i)<=lm; i++)
		for (j=1; j<=n; j++)
		{
			t[i][j]=t[i-1][t[i-1][j]];
			if (t[i][j]) cm[i][j]=min(cm[i-1][j], cm[i-1][t[i-1][j]]);
		}
	rmq();
	scanf("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);
	while (m--)
	{
		if (x==y) z=0; else
		{
			p=lca(x,y);
			z=min(search(x, p), search(y, p));
		}
		if (m<pp) printf("%d\n",z);
		x=(x*a+y*b)%n+1;
		y=(y*c+z*d)%n+1;
	}
}