Cod sursa(job #1154714)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 26 martie 2014 12:33:07
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include<cstdio>
#include<vector>
using namespace std;
void nothing(){
    int i=0;
    i++;
}
struct Road{
    int city,need;
    Road(int city, int need){
        this->city=city;
        this->need=need;
    }
};
const int MAX_N=32000,MAX_LOG_N=15,INF=2000000000;
int anc[MAX_LOG_N+1][MAX_N+1],minA[MAX_LOG_N+1][MAX_N+1];
vector<Road> sons[MAX_N+1];
int level[MAX_N+1];
int n,m,last,x,y,a,b,c,d,lca,z;
void read(){
    int i,city,need;
    scanf("%d%d%d",&n,&m,&last);
    for(i=2;i<=n;i++){
        scanf("%d%d",&city,&need);
        sons[city].push_back(Road(i,need));
        anc[0][i]=city;
        minA[0][i]=need;
    }
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
}
void setAnc(){
    int i,j;
    for(i=1;1<<i<=n;i++)
        for(j=1;j<=n;j++)
            anc[i][j]=anc[i-1][anc[i-1][j]];
}
void dfs(int vertex){
    int i;
    for(i=0;i<sons[vertex].size();i++){
        level[sons[vertex][i].city]=level[vertex]+1;
        dfs(sons[vertex][i].city);
    }
}
void setMinA(){
    int i,j;
    for(i=1;1<<i<=n;i++)
        for(j=1;j<=n;j++)
            minA[i][j]=min(minA[i-1][j],minA[i-1][anc[i-1][j]]);
}
void init(){
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    read();
    setMinA();
    dfs(1);
    setAnc();
}
void setSameLevel(){
    int step=1<<15,l,order=15;
    if(level[x]<level[y])
        swap(x,y);
    l=level[x];
    while(l!=level[y]){
        l+=step;
        if(l<level[y])
            l-=step;
        else
            x=anc[order][x];
        step/=2;
        order--;
    }
}
void setLca(){
    int step=1<<15,order=15,xx=x,yy=y;
    while(order>=0){
        if(anc[order][x]==anc[order][y]||level[x]-step<0)
            nothing();
        else{
            x=anc[order][x];
            y=anc[order][y];
        }
        order--;
        step/=2;
    }
    lca=anc[0][x];
    x=xx;
    y=yy;
}
int minF(int v1,int v2){
    int step=1<<15,order=15,minV=INF;
    while(v1!=v2){
        if(level[v1]-step>=level[v2]){
            if(minA[order][v1]<minV)
                minV=minA[order][v1];
            v1=anc[order][v1];
        }
        order--;
        step/=2;
    }
    return minV;
}
void solve(){
    setSameLevel();
    setLca();
    z=min(minF(x,lca),minF(y,lca));
}
int main(){
    init();
    while(m>0){
        m--;
        solve();
        if(x==y)
            z=0;
        if(m<=last)
            printf("%d\n",z);
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    return 0;
}