Cod sursa(job #913704)

Utilizator ericptsStavarache Petru Eric ericpts Data 13 martie 2013 18:32:26
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
#define maxn 62010*2
#define maxLog 16
#define mp make_pair
#define pb push_back
#define cint const int&
#define forEach(G) for( typeof(G.begin()) it = G.begin(); it != G.end(); ++ it)
vector< pair<int,int> > G[maxn];
int lvl[maxn];
int maxLev;
int first[maxn];
int eul[maxn];
int lg[maxn];
int RMQ[maxLog][maxn];
int best[maxLog][maxn];
int root[maxLog][maxn];
bool viz[maxn];
int N,Q,P;
int CR;

void dfs(cint nod,cint lev){
    ++CR;
    viz[nod] = 1;
    lvl[CR] = lev;
    eul[CR] = nod;
    first[nod] = CR;
    maxLev = max(lev,maxLev);
    forEach(G[nod]){
        if(viz[it->first])continue;
        root[0][it->first] = nod;
        best[0][it->first] = it->second;
        dfs(it->first,lev+1);
        ++CR;
        lvl[CR] = lev;
        eul[CR] = nod;
    }
}

void build(){
    int i,j,x;
    for(i=2;i<=CR;++i)
        lg[i] = lg[i/2]+1;

    for(i=1;i<=CR;++i)
        RMQ[0][i] = lvl[i];

    for(i=1;(1<<i) < CR;++i){
        for(j=1;j + (1 << i) <= CR; ++ j){
            RMQ[i][j] = min(
                            RMQ[i-1][j],
                            RMQ[i-1][j + (1 << (i-1))]
                            );
        }
    }
    for(i=1;(1<<i) <= maxLev; ++ i){
        for(j=1;j <= N; ++ j){
            root[i][j] = root[i-1][root[i-1][j]];
            best[i][j] = min(
                             best[i-1][j],
                             best[i-1][root[i-1][j]]
                             );
        }
    }


}

int ancestor(int nod,int lev){
    int ret = (1 << 30 )- 1,i;
    for(i=0;lev>0;++i){
        if(lev & (1 << i)){
            ret = min(ret,best[i][nod]);
            nod = root[i][nod];
            lev ^= 1 << i;
        }
    }return ret;
}

int LCA(int a,int b)
{
    if(a==b)
        return 0;
    a = first[a],b = first[b];int dif,len;
    if(a > b)
        swap(a,b);
    dif = b-a+1,len = lg[dif];
    return min(RMQ[len][a],RMQ[len][a + dif - (1 << len)]);
}

int query(int x,int y)
{
    int mid = LCA(x,y);
    int levX = lvl[first[x]],levY = lvl[first[y]];
    int left = ancestor(x,levX-mid),right = ancestor(y,levY-mid);
    return min(left,right);
}

int main(){
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);

    scanf("%d %d %d",&N,&Q,&P);int a,b,i;
    int X,Y,A,B,C,D,Z;

    for(i=2;i<=N;++i){
        scanf("%d %d",&a,&b);
        G[i].pb(mp(a,b));
        G[a].pb(mp(i,b));
    }
    dfs(1,1);build();
    scanf("%d %d",&X,&Y);
    scanf("%d %d %d %d",&A,&B,&C,&D);
    for(i=1;i<=Q;++i){
        Z = query(X,Y);
        if(Q-i < P)
            printf("%d\n",Z);
        X = (X*A + Y*B) % N + 1;
        Y = (Y*C + Z*D) % N + 1;
    }

}