Cod sursa(job #1094057)

Utilizator andrettiAndretti Naiden andretti Data 28 ianuarie 2014 21:08:10
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define maxn 32005
#define maxlg 17
#define inf 0x3f3f3f3f
using namespace std;

int n,m,p,u,e;
int X,Y,Z,A,B,C,D;
int lev[maxn],s[maxn],c[maxlg][maxn],f[maxlg][maxn];
int euler[maxn<<2],pos[maxn],rmq[maxlg][maxn<<2],lg[maxn<<2];
vector< pair<int,int> > l[maxn];

void read()
{
    int x,y;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=2;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        l[x].pb(mp(i,y)); l[i].pb(mp(x,y));
    }
    scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
}

void dfs(int k,int level,int val,int father)
{
    lev[k]=level; s[++u]=k; euler[++e]=k;
    if(!pos[k]) pos[k]=e;

    c[0][k]=inf; f[0][k]=k;
    if(u>1) c[1][k]=val,f[1][k]=father;
    for(int i=2;u-(1<<i)+1>0;i++)
     c[i][k]=min(c[i-1][k],c[i-1][s[u-(1<<(i-1))]]),
     f[i][k]=s[u-(1<<i)+1];

    for(unsigned int i=0;i<l[k].size();i++)
     if(!lev[l[k][i].first])
     {
         dfs(l[k][i].first,level+1,l[k][i].second,k);
         euler[++e]=k;
     }
     u--;
}

void RMQ()
{
    for(int i=1;i<=e;i++) rmq[0][i]=euler[i];
    for(int i=2;i<=e;i++) lg[i]=lg[i/2]+1;

    for(int i=1;(1<<i)<e;i++)
     for(int j=1;j+(1<<i)<=e;j++)
     {
         rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
         if(lev[rmq[i][j]]>lev[rmq[i-1][j]])
          rmq[i][j]=rmq[i-1][j];
     }
}

int LCA(int x,int y)
{
    if(pos[x]>pos[y]) swap(x,y);
    x=pos[x]; y=pos[y];

    int k=lg[y-x+1],lca;
    lca=rmq[k][y-(1<<k)+1];
    if(lev[lca]>lev[rmq[k][x]]) lca=rmq[k][x];
    return lca;
}

int query(int x,int y)
{
    int k,sol=inf;
    while(lev[x]!=lev[y])
    {
        k=lg[lev[x]-lev[y]+1];
        sol=min(sol,c[k][x]);
        x=f[k][x];
    }
    return sol;
}

void solve()
{
    int lca;
    for(int i=1;i<=m;i++)
    {
        lca=LCA(X,Y);
        Z=min(query(X,lca),query(Y,lca));
        if(i>=m-p+1) printf("%d\n",Z);

        X=((X*A)%n+(Y*B)%n)%n+1;
        Y=((Y*C)%n+(Z*D)%n)%n+1;
    }
}

int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);

    read();
    dfs(1,1,inf,0);
    RMQ();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}