Cod sursa(job #1674558)

Utilizator margikiMargeloiu Andrei margiki Data 4 aprilie 2016 18:51:18
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
# include <bits/stdc++.h>
# define NR 35000
# define INF 999999999
# define DIM 17
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
vector <int> v[NR];
int i,j,n,m,A,B,C,D,X,Y,Z,niv[NR],Q,P,x,cost;
int best[NR][DIM], T[NR][DIM];

void DFS (int k, int nivel) {
    niv[k]=nivel;

    for (int i=1; i<DIM; ++i) {
        T[k][i]=T[T[k][i-1]][i-1];
        best[k][i]=min(best[k][i-1], best[T[k][i-1]][i-1]);
    }

    for (auto &x: v[k])  //daca nu am mai trecut pe aici
        DFS (x, nivel+1);
}
int query (int X, int Y) {
    int minim=INF;
    if (X==Y) return 0;

    if (niv[X] < niv[Y]) swap(X, Y);
    for (int i=DIM-1; i>=0; --i)
        if (niv[X] - (1<<i)>=niv[Y]) {
            minim=min(minim, best[X][i]);
            X=T[X][i];
        }

    for (int i=DIM-1; i>=0; --i) {
        if (T[X][i]!=T[Y][i]) {
            minim=min(minim, best[X][i]);
            minim=min(minim, best[Y][i]);

            X=T[X][i];
            Y=T[Y][i];
        }
    }
    if (X!=Y) {
        minim=min(minim, min(best[X][0], best[Y][0]));
    }

    return minim;
}
int main ()
{
    f>>n>>Q>>P;

    for (i=2; i<=n; ++i) {
        f>>x>>cost;
        T[i][0]=x; best[i][0]=cost;
        v[x].push_back(i);
    }
    for (int i=0; i<DIM; ++i) best[0][i]=INF;
    best[1][0]=INF; DFS (1, 1);

    f>>X>>Y>>A>>B>>C>>D;
    for (i=1; i<=Q; ++i) {
        Z=query (X, Y);
        if (i>=Q - P + 1) g<<Z<<"\n";

        X=(X*A + Y*B)%n + 1;
        Y=(Y*C + Z*D)%n + 1;
    }

    return 0;
}