Cod sursa(job #2124031)

Utilizator vancea.catalincatalin vancea.catalin Data 6 februarie 2018 20:15:16
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<iostream>
#include<fstream>
#include<vector>
#define DN 33000
#define MAXX 320100
 
using namespace std;
fstream fin("atac.in",ios::in), fout("atac.out",ios::out);
vector<pair<int,int> > v[DN];
int N,M,P,A,B,C,D,x,y,z;
int le,dp[20][DN],dpm[20][DN],log[DN],niv[DN];

void dfs(int nod, int nivel)
{
    niv[nod]=nivel;
    for(auto x:v[nod])
    {
		dfs(x.first,nivel+1);
		dp[0][x.first]=nod;
		dpm[0][x.first]=x.second;
	}
}

int salt(int nod,int pas)
{
	int bit;
	while(pas!=0)
	{
		bit=pas-(pas&(pas-1));
		nod=dp[log[bit]][nod];
		pas=pas-bit;
	}
	return nod;
}
int calc(int nod,int pas)
{
	int bit,minim=MAXX;
	while(pas!=0)
	{
		bit=pas-(pas&(pas-1));
		minim=min(minim,dpm[log[bit]][nod]);
		nod=dp[log[bit]][nod];
		pas=pas-bit;
	}
	return minim;
}

int lca(int x,int y)
{
	int a,b,dif,pas=15;
    if(niv[x]>niv[y]) swap(x,y);
	dif=niv[y]-niv[x];
	y=salt(y,dif);

	//niv[x]==niv[y]
	
	if(x==y) return x;
	
	while(pas>=0)
	{
		a=salt(x,(1<<pas));
		b=salt(y,(1<<pas));
		if(a!=b && a!=0) 
		{
			x=a;
			y=b;
		}
		pas--;
	}
	
	return dp[0][x];
}

int lcamin(int w,int x,int z)
{
	int dif,minim=MAXX;
	if(x==y) return 0;
	if(x!=w)
	{
		dif=niv[x]-niv[w];
		minim=min(minim, calc(x,dif));
	}
	if(y!=w)
	{
		dif=niv[y]-niv[w];
		minim=min(minim, calc(y,dif));
	}
	return minim;
}
 
int main()
{
    int i,j,U,V,w;
    fin>>N>>M>>P;
    for(i=2;i<=N;i++){   
        //u->i cost v
        fin>>U>>V;
        v[U].push_back({i,V});
    }
    dfs(1,1);
    
    for(i=1;(1<<i)<DN;i++)
    {
		for(j=2;j<=N;j++)
		{
			dp[i][j]=dp[i-1][dp[i-1][j]];
			dpm[i][j]=min(dpm[i-1][dp[i-1][j]],dpm[i-1][j]);
		}
	}		
	for(i=0;(1<<i)<DN;i++) log[(1<<i)]=i;
	for(i=1;i<DN;i++) log[i]=max(log[i-1],log[i]);
    
    fin>>x>>y>>A>>B>>C>>D;
    
    for(i=1;i<=M;i++)
    {
        w=lca(x,y);
        z=lcamin(w,x,y);
         
        if(M-P<i)
        {
            fout<<z<<"\n";
        }
        x=(x*A + y*B)%N+1;
        y=(y*C + z*D)%N+1;
         
    }   
     
}