Cod sursa(job #708300)

Utilizator mihai995mihai995 mihai995 Data 6 martie 2012 18:07:14
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=32005,LG=16,inf=1<<30;
int tata[N][LG],cost[N][LG],rez[N*LG],depth[N],n,A,B,Co,D ;
bool use[N];
struct Muchie
{
    int y,c;
};
vector<Muchie> a[N];

ifstream in("atac.in");
ofstream out("atac.out");

inline int min(int a,int b)
{
    return a<b ? a : b;
}

inline void next(int &x,int &y,int z)
{
    x=(A*x+B*y)%n+1;
    y=(Co*y+D*z)%n+1;
}

int C(int x,int L)
{
    int rez=inf;
    for (int i=LG-1;i>=0;i--)
        if (L & (1<<i))
        {
            rez=min(rez,cost[x][i]);
            x=tata[x][i];
        }
    return rez;
}

int T(int x,int L)
{
    for (int i=LG-1;i>=0;i--)
        if (L & (1<<i))
            x=tata[x][i];
    return x;
}

int det(int L,int x,int y)
{
    return min(C(x,depth[x]-L),C(y,depth[y]-L));
}

int lca(int x,int y)
{
    int X,Y;
    if (depth[x]>depth[y])
        x=T(x,depth[x]-depth[y]);
    if (depth[x]<depth[y])
        y=T(y,depth[y]-depth[x]);
    for (int i=LG-1;i>=0;i--)
    {
        X=tata[x][i];
        Y=tata[y][i];
        if (X!=Y)
        {
            x=X;
            y=Y;
        }
    }
    return tata[x][0];
}

void dfs(int x,int d)
{
    int y,c;
    use[x]=true;
    depth[x]=d;
    for (vector<Muchie>::iterator i=a[x].begin();i!=a[x].end();i++)
    {
        y=(*i).y;c=(*i).c;
        if (!use[y])
        {
            dfs(y,d+1);
            tata[y][0]=x;
            cost[y][0]=c;
        }
    }
}

void dinamica()
{
    for (int i=1;i<LG;i++)
        for (int j=1;j<=n;j++)
        {
            tata[j][i]=tata[tata[j][i-1]][i-1];
            cost[j][i]=min(cost[j][i-1],cost[tata[j][i]][i-1]);
        }
}

int main()
{
    int m,p,x,y,c;
    in>>n>>m>>p;
    for (int i=0;i<N;i++)
        for (int j=0;j<LG;j++)
            cost[i][j]=inf;
    for (int i=2;i<=n;i++)
    {
        x=i;
        in>>y>>c;
        a[x].push_back((Muchie){y,c});
        a[y].push_back((Muchie){x,c});
    }
    in>>x>>y>>A>>B>>Co>>D;

    dfs(1,0);
    dinamica();

    for (int i=1;i<=m;i++)
    {
        rez[i]=det(depth[lca(x,y)],x,y);
        next(x,y,rez[i]);
    }
    for (int i=m-p+1;i<=m;i++)
        out<<rez[i]<<"\n";
    return 0;
}