Cod sursa(job #2436007)

Utilizator bluestorm57Vasile T bluestorm57 Data 4 iulie 2019 15:05:00
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
// wish me luck
//Good luck to problems!

// That's better

#include <bits/stdc++.h>

using namespace std;

ifstream f("atac.in");
ofstream g("atac.out");

const int NMAX = 32010;
const int LMAX = 20;
const int inf = 2e9;
vector < pair < int, int> > v[NMAX];
int n,m,p, X, Y, A, B, C, D,  minim;
int k,euler[2 * NMAX], lvl[NMAX], pos[NMAX];
int lg[2 * NMAX], rmq[LMAX][2 * NMAX];
int dp[LMAX][NMAX], cost[LMAX][NMAX];

void dfs(int nod, int level){
    euler[++k] = nod;
    lvl[nod] = level;
    pos[nod] = k;
    for(auto it: v[nod])
        if(!lvl[it.first]){
            dp[0][it.first] = nod;
            cost[0][it.first] = it.second;
            dfs(it.first, level + 1);
            euler[++k] = nod;
        }
}

void buildRMQ(){
    int i,j;
    for(i = 2 ; i <= k ; i++)
        lg[i] = lg[i / 2] + 1;

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

    for(i = 1 ; i <= lg[k] ; i++)
        for(j = 1 ; j <= k - (1 << i) ; j++)
            if(lvl[rmq[i - 1][j]] <= lvl[rmq[i - 1][j + (1 << (i - 1))]])
                rmq[i][j] = rmq[i - 1][j];
            else
                rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}

int LCA(int x, int y){
    x = pos[x];
    y = pos[y];
    if(x > y)
        swap(x, y);
    int dif = (y - x + 1);
    int l = lg[dif];
    if(lvl[rmq[l][x]] < lvl[rmq[l][y - (1 << l) + 1]])
        return rmq[l][x];
    return rmq[l][y - (1 << l) + 1];
}

void buildDP(){
    int i,j;
    for(i = 1 ; (1 << i) <= n ; i++)
        for(j = 1 ; j <= n; j++){
            dp[i][j] = dp[i - 1][dp[i -1][j]];
            cost[i][j] = min(cost[i - 1][j], cost[i - 1][dp[i - 1][j]]);
        }
}

int main(){
    int i,x,y;
    f >> n >> m >> p;
    for(i = 2 ; i <= n ; i++){
        f >> x >> y;
        v[x].push_back(make_pair(i, y));
        v[i].push_back(make_pair(x, y));
    }

    f >> X >> Y >> A >> B >> C >> D;

    dfs(1,1 );
    buildRMQ();
    buildDP();

    int common, cx, cy, difx, dify, up;
    for( i = 1 ; i <= m ; i++){
        //g << X << " " << Y << "\n";
        if(X != Y){
        common = lvl[LCA(X,Y)];
        cx = X;
        cy = Y;
        difx = lvl[X] - common;
        dify = lvl[Y] - common;
        up = 0;
        minim = inf;

        while(difx > 0 && X > 0){
            if(difx & 1){
                minim = min(minim, cost[up][X]);
                X = dp[up][X];
            }
            up++;
            difx /= 2;
        }

        up = 0;
        while(dify > 0 && Y > 0){
            if(dify & 1){
                minim = min(minim, cost[up][Y]);
                Y = dp[up][Y];
            }
            up++;
            dify /= 2;
        }

        if(minim == inf)
            minim = 0;

        X = cx;
        Y = cy;
        }else{
            minim = 0;
        }

        if(i > m - p)
            g << minim << "\n";



        X = (X * A + Y * B) % n + 1;
        Y = (Y * C + minim * D) % n + 1;
    }

    return 0;
}