Cod sursa(job #1046539)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 decembrie 2013 01:50:32
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream cin("atac.in");
ofstream cout("atac.out");
 
const int nmax = 1 << 15;
int N, M, P;
int A, B, C, D;
int X, Y;
vector<int> G[nmax];
int T[16][nmax];
int cost[16][nmax];
int lg[nmax];
int lvl[nmax];
 
void readData() {
    cin >> N >> M >> P;   
    for (int i = 2;i <= N;i++) {
        cin >> T[0][i] >> cost[0][i];
        G[i].push_back(T[0][i]);
        G[T[0][i]].push_back(i);
    }
    cin >> X >> Y >> A >> B >> C >> D;
}
 
void df(int v,int fn) {
    for (const int &w : G[v]) {
        if (w != fn) {
            lvl[w] = lvl[v] + 1;
            df(w,v);
        }
    }
}
 
void compute() {
    for (int i = 2;i <= N;i++) {
        lg[i] = lg[i >> 1] + 1;
    }
 
    for (int i = 1;(1 << i) <= N;i++) {
        for (int j = 1;j <= N;j++) {
            T[i][j] = T[i - 1][T[i - 1][j]];
            cost[i][j] = min(cost[i - 1][j],cost[i - 1][T[i - 1][j]]);
        }
    }
}
 
inline int getLca(int x,int y) {
	while (lvl[x] > lvl[y]) {
        x = T[lg[lvl[x] - lvl[y]]][x];
    }
    while (lvl[y] > lvl[x]) {
        y = T[lg[lvl[y] - lvl[x]]][y];
    }

    if (x == y)  return x;
    for(int l = lg[lvl[x]];l >= 0;l--) {
        if (T[l][x] != T[l][y]) {
            x = T[l][x];
            y = T[l][y];
        }
    }
    return T[0][x];
}
 
inline int query(int x,int y) {
    if (x == y) {
        return 0;
    }
    int lca = getLca(x,y);
    int arr[] = {x,y};
    int ret = int(2e9);
    for (int i = 0;i < 2;i++) {
        x = arr[i];
        int d = lvl[x] - lvl[lca];
        while (d > 0) {
            int l = lg[d];
            ret = min(ret,cost[l][x]);
            x = T[l][x];
            d -= (1 << l);
        }
         
    }
    return ret;
}
 
 
int main()
{
    readData();
    compute();
    df(1,0);
    for (int i = 1;i <= M;i++) {
        int Z = query(X,Y);
        X = (X * A + Y * B) % N + 1;
        Y = (Y * C + Z * D) % N + 1;
        if (i >= M - P + 1) {
            cout << Z << "\n";
        }
    }
    return 0;
}