Cod sursa(job #1933150)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 20 martie 2017 15:01:06
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#include <vector>
#define N 32005
#define log 17
using namespace std;

vector<int> g[N];
int n,m,p,i,j,a,b,c,d,x,y,z,pas,dif,ans,X,Y;
int anc[log][N],cost[log][N],lvl[N];

int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}
void dfs(int nod,int h,int ant)
{
    lvl[nod]=h;
    for(int i=0;i<g[nod].size();i++)
        if(g[nod][i]!=ant)
            dfs(g[nod][i],h+1,nod);
}
int main()
{
    FILE *f1,*f2;
    f1=fopen("atac.in","r");
    f2=fopen("atac.out","w");

    fscanf(f1,"%d%d%d",&n,&m,&p);
    for(i=2;i<=n;i++)
    {
        fscanf(f1,"%d%d",&a,&b);
        g[i].push_back(a);
        g[a].push_back(i);
        anc[0][i]=a;
        cost[0][i]=b;
    }
    fscanf(f1,"%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);

    dfs(1,0,0);

    for(j=1;(1<<j)<=n;j++)
        for(i=1;i<=n;i++)
        {
            anc[j][i]=anc[j-1][anc[j-1][i]];
            cost[j][i]=min(cost[j-1][i],cost[j-1][anc[j-1][i]]);
        }

    while(m--)
    {
        if(lvl[x]<lvl[y])
            swap(x,y);

        dif=lvl[x]-lvl[y];
        ans=1<<30;

        X=x;Y=y;
        for(i=0;(1<<i)<=dif;i++)
            if(dif & (1<<i))
            {
                ans=min(ans,cost[i][x]);
                x=anc[i][x];
            }

        for(i=0;(1<<i)<=n;i++)
            if(anc[i][x]!=anc[i][y])
            {
                ans=min(ans,cost[i][x]);
                ans=min(ans,cost[i][y]);
                x=anc[i][x];
                y=anc[i][y];
            }

        ans=min(ans,cost[0][x]);
        ans=min(ans,cost[0][y]);
        x=anc[0][x];
        y=anc[0][y];

        if(X==Y)
            ans=0;

        if(m<p)
            fprintf(f2,"%d\n",ans);

        x=(X*a + Y*b)%n+1;
        y=(Y*c + ans*d)%n+1;
    }



    /*for(j=0;(1<<j)<=n;j++)
    {
        for(i=1;i<=n;i++)
            printf("%d ",cost[j][i]);
        printf("\n");
    }*/

    return 0;
}