Cod sursa(job #2435723)

Utilizator bluestorm57Vasile T bluestorm57 Data 4 iulie 2019 12:48:53
Problema Atac Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb

#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], father[NMAX], dist[NMAX], Dist[NMAX];
int lg[2 * NMAX], rmq[LMAX][2 * 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]){
            father[it.first] = nod;
            dist[it.first] = it.second;
            Dist[it.first] = Dist[nod] + 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 anotherDFS(int nod, int ancestor){
    while(nod != ancestor){
        minim = min(minim, dist[nod]);
        nod = father[nod];
    }
}

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));
    }

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

    dfs(1,1);
    buildRMQ();

    int common;
    for( i = 1 ; i <= m ; i++){

        if(X != Y){
            common = LCA(X, Y);
            minim = 2e9;
            anotherDFS(X, common);
            anotherDFS(Y, common);
        }else{
            minim = 0;
            common = X;
        }
        if(i > m - p)
            g << minim << "\n";

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

    return 0;
}