Cod sursa(job #606684)

Utilizator crushackPopescu Silviu crushack Data 7 august 2011 23:38:07
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define NMax 30010
#define LNMax 16
#define INF 0x3f3f3f3f
using namespace std;

const char IN[]="atac.in",OUT[]="atac.out";

int N,M,Pt,X,Y,A,B,C,D,R;
int T[NMax][LNMax] , P[NMax][LNMax] , lvl[NMax];
vector<pair<int,int> > ad[NMax];

inline void next(int &x,int &y){
    x= ( 1LL*x*A + 1LL*y*B ) % N +1;
    y= ( 1LL*y*C + 1LL*R*D ) % N +1;
}

void bfs(int x=1,int p=0,int lv=1)
{
    int i;
    lvl[x]=lv;
    P[x][0]=p;
    for (i=1;(1<<i)<=N && P[P[x][i-1]][i-1];++i)
        P[x][i]=P[P[x][i-1]][i-1],T[x][i]=min(T[x][i-1],T[P[x][i-1]][i-1]);

    for (i=0;i<(int)ad[x].size();++i) if (ad[x][i].first!=p)
    {
        T[ad[x][i].first][0]=ad[x][i].second;
        bfs(ad[x][i].first,x,lv+1);
    }
}

int lca(int x,int y)
{
    int step;
    if (lvl[x]<lvl[y]) swap(x,y);

    for (step=1;(1<<step)<=N;++step);
    for(;step;--step)
        if (lvl[x]-(1<<step)>=lvl[y])
            x=P[x][step];
    while (lvl[x]>lvl[y]) x=P[x][0];

    if (x==y) return x;

    for (step=1;(1<<step)<=N;++step);
    for(;step;--step)
        if  (P[x][step]!=P[y][step])
            x=P[x][step],y=P[y][step];
    while (P[x][0]!=P[y][0]) x=P[x][0],y=P[y][0];
    return P[x][0];
}

int getmin(int x,int y)
{
    int step,ret=INF;
    for (step=1;(1<<step)<=N;++step);
    for (;step;--step)
        if (lvl[x]-(1<<step)>=lvl[y])
            ret=min(ret,T[x][step]),x=P[x][step];
    while (x!=y) ret=min(ret,T[x][0]),x=P[x][0];
    return ret;
}

int query(int x,int y)
{
    int z=lca(x,y);
    return min(getmin(x,z),getmin(y,z));
}

int main()
{
    int i,x,y;
    freopen(IN,"r",stdin);
    scanf("%d%d%d",&N,&M,&Pt);
    for (i=2;i<=N;++i) scanf("%d%d",&x,&y),ad[i].push_back(make_pair(x,y)),ad[x].push_back(make_pair(i,y));
    scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
    fclose(stdin);

    bfs();

    freopen(OUT,"w",stdout);
    for (i=0;i<M;++i)
    {
        int r=query(X,Y);R=r;
        if (M-Pt<=i) printf("%d\n",r);
        next(X,Y);
    }
    fclose(stdout);

    return 0;
}