Cod sursa(job #2012123)

Utilizator victoreVictor Popa victore Data 17 august 2017 22:27:24
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<cstdio>
#include<vector>
#define pb(x) push_back(x)

using namespace std;

const int nmax=32005;

int n,m;
int rmq[20][nmax<<1],lg[nmax<<1],first[nmax],euler[nmax<<1],h[nmax<<1],level[nmax];
int tope;
vector<int> g[nmax];

inline int min(int a,int b)
{
    if(a>b)
        return b;
    return a;
}

inline void dfs(int node,int height)
{
    int i;
    h[++tope]=height;
    euler[tope]=node;
    first[node]=tope;
    level[node]=height;
    int cnode;
    for(i=0;i<g[node].size();++i)
    {
        cnode=g[node][i];
        dfs(cnode,height+1);
        h[++tope]=height;
        euler[tope]=node;
    }
}

inline void rmqu()
{
    int i,j,l;
    lg[1]=0;
    for(i=2;i<=tope;++i)
        lg[i]=1+lg[i>>1];
    for(i=1;i<=tope;++i)
        rmq[0][i]=i;
    for(i=1;(1<<i) < tope ; ++i)
        for(j=1; j + (1<<i) <= tope ;++j)
        {
            l=(1<<(i-1));
            rmq[i][j]=rmq[i-1][j];
            if(h[rmq[i-1][j+l]] < h[rmq[i-1][j]])
                rmq[i][j]=rmq[i-1][j+l];
        }
}

inline int lca(int x,int y)
{
    int dif,sol,add,l;
    int a=first[x],b=first[y];
    if(a>b)
    {
        a^=b;
        b=a^b;
        a^=b;
    }
    dif=b-a+1;
    l=lg[dif];
    sol=rmq[l][a];
    add= dif - (1<<l);
    if(h[sol] > h[rmq[l][a+add]])
        sol=rmq[l][a+add];
    return euler[sol];
}

int dp[20][nmax];
int v[20][nmax];

inline void dinamica()
{
    int i,j;
    for(j=1; (1<<j) <= n; ++j)
        for(i=1; i <= n;++i)
        {
            dp[j][i]=min(dp[j-1][i] , dp[j-1][v[j-1][i]]);
            v[j][i]=v[j-1][v[j-1][i]];
        }
}

inline int solve(int x,int y)
{
    int l=level[x]-level[y],node=x,i;
    int ans=2e9;
    for(i=17;i>=0;--i)
        if(l>=(1<<i))
        {
            l-=(1<<i);
            ans=min(ans,dp[i][node]);
            node=v[i][node];
        }
    return ans;
}

inline void compute(int &x,int &y,int a,int b,int c,int d,int z)
{
    int xp=(x*a+y*b)%n+1,yp=(y*c+z*d)%n+1;
    x=xp;
    y=yp;
}

int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    int i,p,y,val;
    scanf("%d%d%d",&n,&m,&p);
    for(i=2;i<=n;++i)
    {
        scanf("%d%d",&y,&val);
        g[y].pb(i);
        dp[0][i]=val;
        v[0][i]=y;
    }
    dfs(1,1);
    rmqu();
    dinamica();
    int ancestor,ans,x,a,b,c,d,t1,t2;
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
    for(i=1;i<=m;++i)
    {
        ancestor=lca(x,y);
        t1=solve(x,ancestor);
        t2=solve(y,ancestor);
        ans=min(t1,t2);
        if(ans==2e9)
            ans=0;
        if(i>m-p)
            printf("%d\n",ans);
        compute(x,y,a,b,c,d,ans);
    }
}