Cod sursa(job #429451)

Utilizator vlad_DVlad Dumitriu vlad_D Data 30 martie 2010 10:18:57
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

#define nmax 33000
int N, M, P;
vector<int> G[nmax], C[nmax];

//
int cost[nmax];
int F[17][nmax]; //father
int LCA[nmax * 2], LEV[nmax * 2];
void go(int nod, int padre, int bombs, int lev) {
    F[0][nod] = padre;
    cost[nod] = bombs;
    LCA[++LCA[0]] = nod; LEV[++LEV[0]] = lev;
    for (int i = 0; i < G[nod].size(); ++i) if (G[nod][i] != padre) {
        go(G[nod][i], nod, C[nod][i], lev + 1);
        LCA[++LCA[0]] = nod; LEV[++LEV[0]] = lev;
    }
}
//
int RMQ[17][nmax * 2];
int SOL[17][nmax * 2];
int POS[nmax];
int FB[17][nmax * 2];
void go_RMQ() {
    for (int i = 1; i <= LCA[0]; ++i) 
        RMQ[0][i] = LEV[i], SOL[0][i] = LCA[i], POS[LCA[i]] = i;
    for (int k = 1; (1 << k) <= LCA[0]; ++k) {
        for (int i = 1; i + (1 << k) - 1 <= LCA[0]; ++i) {
            RMQ[k][i] = RMQ[k-1][i]; SOL[k][i] = SOL[k-1][i];
            if (RMQ[k-1][i + (1 << (k-1))] < RMQ[k][i])
                RMQ[k][i] = RMQ[k-1][i+(1<<(k-1))],
                SOL[k][i] = SOL[k-1][i+(1<<(k-1))];
        } 
    }

    for (int i = 1; i <= N; ++i) FB[0][i] = cost[i];
    for (int k = 1; (1 << k) <= N; ++k) {
        for (int i = 1; i <= N; ++i) if (F[k-1][F[k-1][i]]) {
            F[k][i] = F[k-1][F[k-1][i]];
            FB[k][i] = min(FB[k-1][i], FB[k-1][F[k-1][i]]);
        }
    }
}
int find_lca(int x, int y) {
    if (x == y) return x;
    x = POS[x]; y = POS[y];
    if (y < x) swap(x, y);

    int k = 1;
    while (x - 1 + (1 << k) <= y) k++;
    k--;
    int best = RMQ[k][x], ret = SOL[k][x];
    if (RMQ[k][y - (1 << k) + 1] < best) ret = SOL[k][y - (1<<k) + 1];
    return ret;
}
int get_min(int a, int padre) {
    int dif = LEV[POS[a]] - LEV[POS[padre]];
    if (dif == 0) return 111111;
    int k = 0;
    int best = 111111;
    for (k = 0; k < 17; ++k) if (dif & (1 << k)) {
        if (FB[k][a] < best) best = FB[k][a];
        a = F[k][a];
    }
    return best;
}
int main() {
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
    scanf("%d %d %d", &N, &M, &P);
    for (int i = 2; i <= N; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        G[i].push_back(u); C[i].push_back(v);
        G[u].push_back(i); C[u].push_back(v);
    }
    //prepare the graph
    go(1, 0, nmax * 4, 0);
    go_RMQ();
    
    int X, Y, A, B, C, D;
    scanf("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);    
    for (int i = 1; i <= M; ++i) {
        int LOL = find_lca(X, Y);
        int Z = min(get_min(X, LOL), get_min(Y, LOL));
        if (Z > 100000) Z = 0;
        if (i + P > M) printf("%d\n", Z);

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