Cod sursa(job #1000212)

Utilizator assa98Andrei Stanciu assa98 Data 22 septembrie 2013 14:10:33
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

//lca+graf

const int MAX_N=32100;

int e[3*MAX_N];
int v[3*MAX_N];

int f[MAX_N];

vector<int> A[MAX_N];
int h[MAX_N];

int LOG[3*MAX_N];
int rmq[20][3*MAX_N];



void pregen(int n) {
    for(int i=1;i<=n;i++) {
        rmq[0][i]=i;
    }

    for(int k=1;(1<<k)<=n;k++) {
	    for(int i=1;(i+(1<<k)-1)<=n;i++) {
            if(v[rmq[k-1][i]]<v[rmq[k-1][i+(1<<(k-1))]]) {
                rmq[k][i]=rmq[k-1][i];
            }
            else {
                rmq[k][i]=rmq[k-1][i+(1<<(k-1))];
            }
        }
    }

    LOG[1]=0;
    for(int i=2;i<=n;i++)
        LOG[i]=LOG[i/2]+1;

}

int lca(int x,int y) {
    x=f[x];
    y=f[y];
    if(x>y)
        swap(x,y);

    int poz;
    int k=LOG[y-x+1];
    if(v[rmq[k][x]]<v[rmq[k][y-(1<<k)+1]]) {
        poz=rmq[k][x];
    }
    else {
       poz=rmq[k][y-(1<<k)+1];
    }

    return e[poz];
}

void dfs(int nod,int lv) {
    e[++e[0]]=nod;
    v[e[0]]=lv;
    f[nod]=e[0];
    h[nod]=lv;

    for(vector<int>::iterator it=A[nod].begin(); it!=A[nod].end(); ++it) {
        dfs(*it,lv+1);

        e[++e[0]]=nod;
        v[e[0]]=lv;
    }
}

//smen

int cost[MAX_N];
int dad[MAX_N];

int str[20][MAX_N];
int c[20][MAX_N];

void smen(int n) {
    for(int i=1;i<=n;i++) {
        str[0][i]=dad[i];
        c[0][i]=cost[i];
    }

    for(int k=1;(1<<k)<=n;k++) {
        for(int i=1;i<=n;i++) {
            str[k][i]=str[k-1][str[k-1][i]];
            c[k][i]=min(c[k-1][i],c[k-1][str[k-1][i]]);
        }
    }
}


int ans(int y,int x) {  // h[x]>h[y]
    int dif=h[x]-h[y];
    int sol=(1<<30);
    for(int i=0;(1<<i)<=dif;i++) {
        if((1<<i)&dif) {
            sol=min(sol,c[i][x]);
            x=str[i][x];
        }
    }
    return sol;
}

int query(int x,int y) {
    if(x==y) {
        return 0;
    }

    int a=lca(x,y);
    return min( ans(a,x),ans(a,y) );
}

int main() {
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);

    for(int i=2;i<=n;i++) {
        int a,t;
        scanf("%d%d",&a,&t);
        A[a].push_back(i);
        dad[i]=a;
        cost[i]=t;
    }
    
    dfs(1,0);
    pregen(e[0]);
    smen(n);

    int x,y,a,b,c,d;
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
    //fprintf(stderr,"%d %d %d %d %d %d\n",x,y,a,b,c,d);


    for(int i=1;i<=m;i++) {
        //fprintf(stderr,"%d %d\n",x,y);
        int z=query(x,y);
        
        if(i>=m-p+1) {
            printf("%d\n",z);
        }

        x=(a*x+b*y)%n+1;
        y=(c*y+d*z)%n+1;
    }
    return 0;
}