Cod sursa(job #1987533)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 30 mai 2017 23:42:46
Problema Atac Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <stdio.h>
#include <stdlib.h>
int lista[32001],nod[64001],drum[64001],next[64001],nr,timp;
int s[32001][17],dr[32001][17],ti[32001],to[32001];
void add(int x,int y,int v)
{
    nr++;
    nod[nr]=y;
    drum[nr]=v;
    next[nr]=lista[x];
    lista[x]=nr;
}
void dfs(int x)
{
    int z;
    ti[x]=++timp;
    z=lista[x];
    while(z)
    {
        dfs(nod[z]);
        z=next[z];
    }
    to[x]=++timp;
}
int stramos(int x,int y)
{
    return (ti[x]<=ti[y] && to[y]<=to[x]);
}
int lca(int x,int y)
{
    if(x==y) return x;
    if(stramos(x,y)) return x;
    if(stramos(y,x)) return y;
    int pas=16,z;
    while(pas+1)
    {
        z=s[x][pas];
        if(!stramos(z,y))
            x=z;
        pas--;
    }
    return s[x][0];
}
int min(int x,int y)
{
    if(x<y) return x;
    return y;
}
int query(int x,int y)
{
    int pas=16,z=0,r=1000000;
    while(pas+1)
    {
        z=s[y][pas];
        if(!stramos(z,x)){
            r=min(dr[y][pas],r);
            y=z;
        }
        pas--;
    }
    return min(r,dr[y][0]);
}
int main()
{
    int n,m,p,i,u,v,z,j,x,y,a,b,c,d,k,xx,yy;
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    for(i=2; i<=n; i++)
    {
        scanf("%d%d",&u,&v);
        add(u,i,v);
    }
    add(0,1,0);
    for(i=1; i<=n; i++)
    {
        z=lista[i];
        while(z)
        {
            dr[nod[z]][0]=drum[z];
            s[nod[z]][0]=i;
            z=next[z];
        }
    }
    for(j=1; j<=16; j++)
        for(i=1; i<=n; i++)
        {
            dr[i][j]=min(dr[dr[i][j-1]][j-1],dr[i][j-1]);
            s[i][j]=s[s[i][j-1]][j-1];
        }
    dfs(0);
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
    for(i=1; i<=m; i++)
    {
        k=lca(x,y);
        z=0;
        if(x==y)
            z=0;
        else
            if(k==x)
                z=query(x,y);
            else
                if(k==y)
                    z=query(y,x);
                else
                    z=min(query(k,x),query(k,y));
        xx=x;
        yy=y;
        x=((long long)xx*a+(long long)yy*b)%n+1;
        y=((long long)yy*c+(long long)z*d)%n+1;
        if(i>=m-p+1)
            printf("%d\n",z);
    }

    return 0;
}