Cod sursa(job #1099364)

Utilizator Theorytheo .c Theory Data 5 februarie 2014 19:45:11
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

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

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

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

int T[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) {

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


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

        if(F[G[nod][i].first]) continue;
        H[0][G[nod][i].first] = nod;
        C_min[0][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 = 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; (1 << i) <= N; ++i)
        for(int j = 1; j <= N; ++j) {

                if( (1 << i) >= Level_nod[j]) continue;
            H[i][j] = H[i - 1][H[i - 1][j]];
            C_min[i][j] = C_min[i - 1][j];
            if(C_min[i][j] > C_min[i - 1][H[i - 1][j]])
                C_min[i][j] = C_min[i - 1][H[i - 1][j]];
    }
}

int query(int X, int Y) {


    if(X == Y) return 0;
    int st = F[X]; int dr = F[Y]; if(st > dr) swap(st, dr);

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

   if(Level[sol] > Level[rmq[lgg][dr - l1 + 1]])
        sol = rmq[lgg][dr - l1 + 1];

   int LCA = Euler[sol];

   fout << LCA <<'\n';
   int min_cost = (1<<30);
   int arr[] = {X, Y};
   for(int i = 0 ;i < 2; ++i){

        int x = arr[i];
        int d = Level_nod[x] - Level_nod[LCA];

        while(d > 0) {

            int l = lg[d];
            min_cost = min(min_cost, C_min[l][x]);
            x = H[l][x];
            d -= (1 << l);
        }
   }

   return min_cost;


}


int main() {

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

    int LCA;

    int Z; int min_cost;


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

        min_cost = query(X, Y);
        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;
}