Cod sursa(job #1106701)

Utilizator Theorytheo .c Theory Data 13 februarie 2014 02:18:54
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("atac.in");
ofstream fout ("atac.out");

const int NMAX = 32109;

int N; int M; int X; int Y; int A; int B; int C2; int D;int P;

int euler[NMAX * 2]; int level[NMAX * 2]; bool see[NMAX]; int first[NMAX];int T[NMAX];

int rmq[17][NMAX * 2]; int C[17][NMAX]; int TT[17][NMAX];int lg[NMAX * 2];

int l[NMAX];

vector<pair <int, int> > G[NMAX];

void read() {

    fin >> N >> M >> P;
    for(int i = 2; i <= N; ++i) {
        int x, cost;
        fin >> x >> cost;
        G[x].push_back(make_pair(i, cost));
        G[i].push_back(make_pair(x, cost));
    }

    fin >> X >> Y >> A >> B >> C2 >> D;
}

void dfs(int nod, int lev) {

    see[nod] = true;
    euler[++euler[0]] = nod;
    level[++level[0]] = lev;
    first[nod] = euler[0];
    l[nod] = lev;

    for(unsigned i = 0 ;i < G[nod].size(); ++i)
        if(see[G[nod][i].first] == false) {

            dfs(G[nod][i].first, lev + 1);
            euler[++euler[0]] = nod;
            level[++level[0]] = lev;

            T[G[nod][i].first] = nod;
            C[0][G[nod][i].first] = G[nod][i].second;
        }
}

void smen() {

    for(int i = 2; i <= euler[0]; ++i)
        lg[i] = lg[i / 2] + 1;

    for(int i = 1; i <= N; ++i)
        TT[0][i] = T[i];


    for(int i = 1; (1 << i) <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            TT[i][j] = TT[i - 1][TT[i - 1][j]];
            C[i][j] = min(C[i - 1][j], C[i - 1][TT[i - 1][j]]);
    }

}

void RMQ() {

    for(int i = 1; i <= euler[0]; ++i)
        rmq[0][i] = i;

    for(int i = 1; (1 << i) <= euler[0]; ++i) {
        int l = 1 << (i - 1);
        for(int j = 1; j <= euler[0] - (1 << i) + 1; ++j) {
            rmq[i][j] = rmq[i - 1][j];
            if(level[rmq[i][j]] > level[rmq[i - 1][j + l]])
                rmq[i][j] = rmq[i - 1][j + l];
        }
    }
}

int LCA(int x, int y) {

    int st = first[x]; int dr = first[y];
    if(st > dr) swap(st, dr);

    int dif = dr - st + 1;
    int lgg = lg[dif];
    int bucket =  (1 << lg[dif]);

    int answ = rmq[lgg][st];

    if(level[answ] > level[rmq[lgg][st + dif - bucket]])
        answ = rmq[lgg][st + dif - bucket];
    return euler[answ];
}

int findm(int X, int Y) {

    int sol = (1 << 30);int l1 = l[X]; int l2 = l[Y];

    while(l1 > l2) {

        int dif = l1 - l2;
        sol = min(sol, C[lg[dif]][X]);
        X = TT[lg[dif]][X];
        l1 = l[X];
    }

    return sol;

}

void solve() {


    dfs(1, 0);
    smen();
    RMQ();

    for(int i = 1; i <= M; ++i) {

        int lca = LCA(X, Y);
        int find_cost = min(findm(X, lca) , findm(Y, lca));

        if(i > M - P) fout << find_cost <<'\n';

        X = (X * A + Y * B) % N + 1;
        Y = (Y * C2 + find_cost * D) % N + 1;
    }

}

int main() {

    read();

    solve();

    return 0;

}