Cod sursa(job #2079825)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 1 decembrie 2017 21:16:40
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
# include <fstream>
# include <vector>
# define DIM 32010
# define INF 1000000000
# define f first
# define s second
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
vector<pair<int,int> > Lista[DIM];
int t[17][DIM],D[17][DIM],niv[DIM];
int n,m,p,i,j,step,x,y,cost,a,b,c,d,xi,yi,val;
void dfs(int nc){
    for(int i=0;i<Lista[nc].size();i++){
        int nv=Lista[nc][i].f;
        int cost=Lista[nc][i].s;
        if(!niv[nv]){
            niv[nv]=niv[nc]+1;
            D[0][nv]=cost;
            t[0][nv]=nc;
            dfs(nv);
        }
    }
}
int main () {
    fin>>n>>m>>p;
    for(i=2;i<=n;i++){
        fin>>y>>cost;
        x=i;
        Lista[x].push_back(make_pair(y,cost));
        Lista[y].push_back(make_pair(x,cost));
    }
    niv[1]=1;
    dfs(1);
    for(j=1,step=2;step<=n;step*=2,j++)
        for(i=1;i<=n;i++){
            t[j][i]=t[j-1][t[j-1][i]];
            D[j][i]=min(D[j-1][i],D[j-1][t[j-1][i]]);
        }
    fin>>x>>y>>a>>b>>c>>d;
    for(i=m;i>=1;i--){
        xi=x;
        yi=y;
        if(x==y){
            val=0;
            if(i<=p)
                fout<<val<<"\n";
            x=xi;
            y=yi;
            x=(x*a+y*b)%n+1;
            y=(y*c+val*d)%n+1;
            continue;
        }
        if(niv[x]<niv[y])
            swap(x,y);
        val=INF;
        for(step=1,j=0;step<=n;step*=2,j++);
        for(;step;step/=2,j--)
            if(niv[x]-step>=niv[y]){
                val=min(val,D[j][x]);
                x=t[j][x];
            }
        if(x==y){
            if(i<=p)
                fout<<val<<"\n";
            x=xi;
            y=yi;
            x=(x*a+y*b)%n+1;
            y=(y*c+val*d)%n+1;
            continue;
        }
        for(step=1,j=0;step<=n;step*=2,j++);
        for(;step;step/=2,j--)
            if(t[j][x]!=t[j][y]){
                val=min(val,D[j][x]);
                val=min(val,D[j][y]);
                x=t[j][x];
                y=t[j][y];
            }
        val=min(val,D[0][x]);
        val=min(val,D[0][y]);
        if(i<=p)
            fout<<val<<"\n";
        x=xi;
        y=yi;
        x=(x*a+y*b)%n+1;
        y=(y*c+val*d)%n+1;
    }
    return 0;
}