Cod sursa(job #1720322)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 21 iunie 2016 23:35:07
Problema Atac Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<cstdio>
#include<vector>
#define MAXN 32010
#define MAXLOG 20
#define INF 1000000000
using namespace std;
vector<pair<int,int> > g[MAXN];
int n,depth[MAXN],dad[MAXLOG][MAXN],best[MAXLOG][MAXN];
void DFS(int node){
    int i;
    depth[node]=depth[dad[0][node]]+1;
    for(i=0;i<g[node].size();i++)
        if(g[node][i].first!=dad[0][node]){
            dad[0][g[node][i].first]=node;
            best[0][g[node][i].first]=g[node][i].second;
            DFS(g[node][i].first);
        }
}
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
void Precompute(){
    int i,j;
    for(i=1;i<MAXLOG;i++)
        for(j=1;j<=n;j++){
            dad[i][j]=dad[i-1][dad[i-1][j]];
            best[i][j]=minimum(best[i-1][j],best[i-1][dad[i-1][j]]);
        }
}
int Query(int x,int y){
    int answer=INF,i;
    if(depth[x]>depth[y]){
        for(i=0;i<MAXLOG;i++)
            if((depth[x]-depth[y])&(1<<i)){
                answer=minimum(answer,best[i][x]);
                x=dad[i][x];
            }
    }
    else{
        for(i=0;i<MAXLOG;i++)
            if((depth[y]-depth[x])&(1<<i)){
                answer=minimum(answer,best[i][y]);
                y=dad[i][y];
            }
    }
    for(i=MAXLOG-1;i>=0;i--)
        if(dad[i][x]!=dad[i][y]){
            answer=minimum(answer,minimum(best[i][x],best[i][y]));
            x=dad[i][x];
            y=dad[i][y];
        }
    if(x!=y)
        answer=minimum(answer,minimum(best[0][x],best[0][y]));
    if(answer==INF)
        return 0;
    return answer;
}
int main(){
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    int m,p,x,y,z,a,b,c,d,i;
    scanf("%d%d%d",&n,&m,&p);
    for(i=2;i<=n;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(make_pair(i,y));
        g[i].push_back(make_pair(x,y));
    }
    DFS(1);
    Precompute();
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
    for(i=1;i<=m;i++){
        z=Query(x,y);
        if(m-p<i)
            printf("%d\n",z);
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    return 0;
}