Cod sursa(job #220859)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 13 noiembrie 2008 14:49:53
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.29 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define INF 100000
#define INF2 100000000
#define FIN "atac.in"
#define FOUT "atac.out"
#define N 33000
using namespace std;
int n,m,p;
vector<int> cine[N],cost[N];
int a,b,c,d,x,y,xp,yp;
int lev[N];
void scan(){
    int i;
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    for (i=2;i<=n;++i){
        scanf("%d%d",&a,&b);
        cine[i].push_back(a);
        cost[i].push_back(b);
        cine[a].push_back(i);
        cost[a].push_back(b);
    }
}
vector<int> euler,sol,high;
int z,viz[N],pozi[N],k=0;
int t1[N],t2[N],tt;
int tata[N],last[N];
void do_euler(int x,int level,int las,int c){
    int i;
    viz[x]=1;lev[x]=level;
    tata[x]=las;
    last[x]=c;
    t1[x]=++tt;
    euler.push_back(x);
    high.push_back(level);
    int k;
    k=euler.end()-euler.begin()-1;
    if (pozi[x]>k)
        pozi[x]=k;
    for (i=0;i<cine[x].end()-cine[x].begin();++i)
        if (!viz[cine[x][i]]){
            do_euler(cine[x][i],level+1,x,cost[x][i]);
            euler.push_back(x);
            high.push_back(level);
            ++tt;
        }
    t2[x]=tt;
}
int val,pos,start,finish;
int arb[1000000];
void update(int nod,int l,int r){
    if (l==r){
        arb[nod]=val;
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) update(2*nod,l,mid);
    else          update(2*nod+1,mid+1,r);
    if (high[arb[2*nod]]>high[arb[2*nod+1]])
        arb[nod]=arb[2*nod+1];
    else
        arb[nod]=arb[2*nod];
}
int lca;
void query(int nod,int l,int r){
    if (start<=l && r<=finish){
        if (high[arb[nod]]<high[lca] || lca==0)
            lca=arb[nod];
        return;
    }
    int mid;
    mid=(l+r)>>1;
    if (start<=mid) query(2*nod,l,mid);
    if (mid<finish) query(2*nod+1,mid+1,r);
}
void pre_arbint(){
    int nn=euler.size()-1,i;
    for (i=1;i<=nn;++i){
        pos=i;
        val=i;
        update(1,1,nn);
    }
}
int str[N][20],best[N][20];
void calc(){
    int i,j;
    //printf("%d\n",n);
    for (i = 0; i <= n; ++i){
        str[i][0] = tata[i];
        best[i][0] = last[i];
    }
    for (i = 1; i <= n; ++i)
        for (j = 1; (1 << j) <= n; ++j)
            best[i][j]=str[i][j]=INF2;
    for (i = 1; i <= n; ++i)
        for (j = 1; (1 << j) <= n; ++j)
            str[i][j] = str[str[i][j-1]][j-1];
    for (i = 1; i <= n; ++i)
        for (j = 1; (1 << j) <= n; ++j)
            best[i][j]=min(best[i][j-1],best[str[i][j-1]][j-1]);
   /* for (i=1;i<=n;++i){
        for (j=0;(1 << j)<=n;++j)
            printf("(%d %d) ",str[i][j],best[i][j]);
        printf("\n");
    }*/
}
int level[]={0,1,2,3,3,2,3,3};
int rez_rmq;
void query_rmq(int x,int y){
    int p,q,f,j,now;
    p=lev[x];
    q=lev[y];
    f=p-q;now=x;
    //fprintf(stderr,"%d %d\n",x,y);
    while (f){
        for (j=0;(1<<j)<f;++j);if (j)--j;
        //fprintf(stderr,"%d %d %d %d\n",x,f,now,j);
        rez_rmq=min(rez_rmq,best[now][j]);
        now=str[now][j];
        p=lev[now];
        f=p-q;
    }
}
void solve(){
    int i,s2,s1,bla_now;
    for (i=1;i<=n;++i)
        pozi[i]=INF;
    euler.push_back(0);
    high.push_back(0);
    do_euler(1,1,0,0);
    pre_arbint();
    calc();
    sol.push_back(0);
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
    for (i=1;i<=m;++i){
        if (t1[x]<t1[y] && t2[y]<t2[x])
            lca=x;
        else if(t1[y]<t1[x] && t2[x]<t2[y])
            lca=y;
        else{
            lca=0;
            s1=pozi[x];
            s2=pozi[y];
            start=min(s1,s2);
            finish=max(s1,s2);
            query(1,1,euler.size()-1);
            lca=euler[lca];
        }
        rez_rmq=INF2;
        query_rmq(x,lca);
        bla_now=rez_rmq;
        rez_rmq=INF2;
        query_rmq(y,lca);
        bla_now=min(bla_now,rez_rmq);
        sol.push_back(bla_now);
        //printf("%d ",bla_now);
        xp=(x*a+y*b)%n+1;
        yp=(y*c+bla_now*d)%n+1;
        //printf("%d %d %d %d %d\n",x,y,xp,yp,bla_now);
        x=xp;
        y=yp;

        //sol=min(search(x,lca),search(y,lca));
    }
}
void print(){
    int i;
    for (i=sol.size()-p;i<sol.size();++i)
        printf("%d\n",sol[i]);
}
main(){
    scan();
    solve();
    print();
}