Cod sursa(job #1098974)

Utilizator Theorytheo .c Theory Data 5 februarie 2014 13:15:48
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 32009;
const int INF = (1 << 30);

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

int T[NMAX]; int Cost[NMAX]; bool see[NMAX];int lg[NMAX];int H[20][2 * NMAX];int C_min[20][2 * NMAX];

int Euler[NMAX * 2]; int Arb[4 * NMAX];int min_ind;int Level[2 * NMAX]; int Level_nod[NMAX];int rmq[20][NMAX * 2];

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

int F[NMAX];


void read() {

    fin >> N >> M >> P;

    for(int i = 2; i <= N; ++i) {

        int u, v;
        fin >> u >> v;
        G[i].push_back(make_pair(u, v));
        G[u].push_back(make_pair(i, v));
    }

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

void dfs(int nod, int level) {

    see[nod] = true; int cost;
    Euler[++Euler[0]] = nod;

    F[nod] = Euler[0];
    Level[Euler[0]] = level;
    Level_nod[nod] = level;

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

        if(see[G[nod][i].first] == false) {

            T[G[nod][i].first] = nod;
            Cost[G[nod][i].first] = G[nod][i].second;

            dfs(G[nod][i].first, level + 1);

            Euler[++Euler[0]] = nod;
            Level[Euler[0]] = level;

        }
    }
}

void rmq_arbore() {

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

    for(int i = 0 ; i <= lg[N]; ++i)
        for(int j = 1; j <= N; ++j)
            C_min[i][j] = INF;

    for(int i = 1; i <= N; ++i) {
        H[0][i] = T[i];
        C_min[0][i] = Cost[i];
    }

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

    for(int i = 1; (1 << i) <= Euler[0]; ++i)
        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 + (1 << (i - 1))]])
                rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
        }


    for(int i = 1; i <= lg[N]; ++i)
        for(int j = 1; j <= N; ++j) {
            H[i][j] = H[i - 1][H[i - 1][j]];
            C_min[i][j] = min(C_min[i - 1][j], C_min[i - 1][H[i - 1][j]]);
    }
}

int query_cost(int X, int Y) {

    int l1 = Level_nod[X]; int l2 = Level_nod[Y];
    int min_value = (1 << 30);
    while(l1 != l2) {

        min_value = min(C_min[lg[l1 - l2]][X], min_value);
        X = H[lg[l1 - l2]][X];
        l1 = Level_nod[X];
        //fout << l1 <<" " << l2 <<'\n';
    }
    return min_value;
}

int query(int st, int dr) {

   int dif = dr - st + 1;
   int lgg = lg[dif];
   int l1 = 1 << lg[dif];
   int sh = dif - l1;
    int sol = rmq[lgg][st];

   if(Level[sol] > Level[rmq[lgg][st + sh]])
        sol = rmq[lgg][st + sh];
   return Euler[sol];

}


int main() {

    read();
    dfs(1, 0);
    rmq_arbore();

    int LCA;

    int Z; int min_cost;
    if(X == Y) min_cost = 0 ;
    else {

        min_ind = 0;
        LCA = query(min(F[X], F[Y]), max(F[Y], F[X]));
        min_cost = min(query_cost(X, LCA), query_cost(Y, LCA));
    }

    X = (X * A + Y * B) % N + 1;
    Y = (Y * C + min_cost * D) % N + 1;

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


        if(X == Y)
            min_cost = 0;
        else {
            LCA = query(min(F[X], F[Y]), max(F[Y], F[X]));
            min_cost = min(query_cost(X, LCA), query_cost(Y, LCA));
            if(i >= M - P)
                fout << min_cost <<'\n';

        }

        X = (X * A + Y * B) % N + 1;
        Y = (Y * C + min_cost * D) % N + 1;

    }


    return 0;
}