Cod sursa(job #2337354)

Utilizator shantih1Alex S Hill shantih1 Data 6 februarie 2019 12:14:52
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmx 32005

using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");

int n,i,j,k,m,p,ne,nd,x,y,A,B,C,D,X,Y,Z;
int lg[2*nmx],f[nmx],h[nmx],id[nmx];

struct per
{	int x,c;	} qe[17][2*nmx],qg[nmx][17],eu[2*nmx];
vector<per> ad[nmx];

void euler(int nd,int h,int v)
{
	eu[++ne]={nd,h};
	f[nd]=ne;
	id[h]=nd;
	
	qg[nd][0]={id[h-1],v};
	for(i=1;i<=lg[h];i++)
	{
		qg[nd][i].c=min(qg[nd][i-1].c, qg[id[h-(1<<(i-1))]][i-1].c);
		qg[nd][i].x=id[h-(1<<i)];
	}
	
	for(auto i:ad[nd])
		if(::h[i.x]==0)
		{
			::h[i.x]=h+1;
			
			euler(i.x,h+1,i.c);
			
			eu[++ne]={nd,h};
			f[nd]=ne;
		}
}
int lca(int x,int y)
{
	if(x==y)	return x;
	int l;
	if(f[x]>f[y])
	{	l=x;	x=y;	y=l;	}
	l=lg[f[y]-f[x]];
	
	per a=qe[l][f[y]];
	per b=qe[l][f[x]+(1<<l)-1];
	if(a.c<=b.c)	return eu[a.x].x;
	return eu[b.x].x;
}
int mn(int x,int y)
{
	int mn=100005;
	if(x==y)	return mn;
	int l=lg[h[y]-h[x]];
	
	while(h[y]>h[x])
	{
		mn=min(mn, qg[y][l].c);
		y=qg[y][l].x;
		l=lg[h[y]-h[x]];
	}
	return mn;
}

int main() {
	
	fin>>n>>m>>p;
	for(i=2;i<=n;i++)
	{
		fin>>k>>j;
		ad[i].push_back({k,j});
		ad[k].push_back({i,j});
	}
	
	lg[0]=-1;
	for(i=1;i<=2*n;i++)
		lg[i]=lg[i-1]+((i&(i-1))==0);
	
	h[1]=1;
	euler(1,1,0);
	
	for(i=1;i<=ne;i++)
		qe[0][i]={i, eu[i].c};
	
	for(i=1;i<=lg[ne];i++)
		for(j=1<<i;j<=ne;j++)
		{
			qe[i][j]=qe[i-1][j-(1<<(i-1))];
			if(qe[i-1][j].c<qe[i][j].c)
				qe[i][j]=qe[i-1][j];
		}
		
	fin>>X>>Y>>A>>B>>C>>D;
	while(m--)
	{
		nd=lca(X,Y);
		Z=min(mn(nd,X), mn(nd,Y));
		if(X==Y)	Z=0;
		
		if(m<p)
			fout<<Z<<"\n";
		
		X=(X*A+Y*B)%n+1;
		Y=(Y*C+Z*D)%n+1;
	}
}