Cod sursa(job #2435773)

Utilizator bluestorm57Vasile T bluestorm57 Data 4 iulie 2019 13:07:59
Problema Atac Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 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];
vector < pair < int, int > > ve[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]){
            for(auto el: ve[nod]){
                ve[it.first].push_back(make_pair(el.first, min(el.second, it.second)));
            }
            ve[it.first].push_back(make_pair(nod, it.second));

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

    /*for(i = 1 ; i <= n ; i++){
        for(auto it: ve[i])
            g << "( " << it.first << "," << it.second << ") ";
        g << "\n";
    }

    return 0;*/
    int common;
    for( i = 1 ; i <= m ; i++){

        if(X != Y){
            common = LCA(X, Y);
            minim = 2e9;
            for(auto it: ve[X])
                if(it.first == common)
                    minim = min(minim, it.second);
            for(auto it: ve[Y])
                if(it.first == common)
                    minim = min(minim, it.second);
            //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;
}