Cod sursa(job #736415)

Utilizator TudorDDodoiu Tudor TudorD Data 18 aprilie 2012 16:23:53
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>
#include <vector>
using namespace std;
int l[32001],two[64000],f[15][32001],first[32000],e[64000],ec,rmq[16][64000],v[15][32001];
struct str{int x,d;};
vector <str> g[32001];
inline int min(int x,int y){if (x<y) return x;else return y;}
inline void swap(int &x,int &y){int aux=x;x=y;y=aux;}
inline int lca(int x,int y){x=first[x];y=first[y];if (x>y) swap(x,y);int aux=two[y-x+1];return min(rmq[aux][x],rmq[aux][y-(1<<aux)+1]);}
void dfs(int x)
{
vector <str>::iterator it;
++ec;
e[ec]=x;
first[x]=ec;
for (it=g[x].begin();it!=g[x].end();++it)
if (!l[it->d])
{
l[it->d]=l[x]+1;
f[0][it->d]=x;
v[0][it->d]=it->x;
dfs(it->d);
++ec;
e[ec]=x;
}
}
int main()
{
int n,m,p,i,j,x,y,x2,y2,a,b,c,d,aux,aux2,sol;
str auxstr;
freopen("atac.in","r",stdin);
freopen("atac.out","w",stdout);
scanf("%d %d %d\n",&n,&m,&p);
for (i=2;i<2*n;++i)
two[i]=two[i/2]+1;
for (i=2;i<=n;++i)
{
scanf("%d %d\n",&x,&y);
auxstr.x=y;
auxstr.d=x;
g[i].push_back(auxstr);
auxstr.d=i;
g[x].push_back(auxstr);
}
l[1]=1;
v[0][1]=0x3f3f3f3f;
dfs(1);
for (i=1;i<2*n;++i)
rmq[0][i]=l[e[i]];
for (i=1;1<<i<2*n;++i)
for (j=1;j<=2*n-(1<<i);++j)
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
for (i=1;1<<i<=n;++i)
{
v[i][1]=0x3f3f3f3f;
for (j=2;j<=n;++j)
{
f[i][j]=f[i-1][f[i-1][j]];
v[i][j]=min(v[i-1][j],v[i-1][f[i-1][j]]);
}
}
scanf("%d %d %d %d %d %d",&x,&y,&a,&b,&c,&d);
for (;m;--m)
{
if (x==y)
sol=0;
else
{
x2=x;
y2=y;
aux=lca(x,y);
sol=0x3f3f3f3f;
while (l[x2]>aux)
{
aux2=two[l[x2]-aux];
sol=min(sol,v[aux2][x2]);
x2=f[aux2][x2];
}
while (l[y2]>aux)
{
aux2=two[l[y2]-aux];
sol=min(sol,v[aux2][y2]);
y2=f[aux2][y2];
}
}
if (m<=p)
printf("%d\n",sol);
x2=(x*a+y*b)%n+1;
y2=(y*c+sol*d)%n+1;
x=x2;
y=y2;
}
return 0;
}