Cod sursa(job #2614689)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 12 mai 2020 15:18:47
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <bits/stdc++.h>

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

std::vector < std::pair < int, int > > edge[32005];
int parent[16][32005];
int rmq[16][32005];
int level[32005];
bool visited[32005];

void findParents (int node){
    visited[node] = true;
    for (int i=0; i<edge[node].size(); i++){
        int next = edge[node][i].first;
        if (visited[next] == false){
            level[next ] = level[node] + 1;
            parent[0][next] = node;
            rmq[0][next] = edge[node][i].second;
            for (int j=1; parent[j-1][parent[j-1][next]] != 0; j++){
                parent[j][next] = parent[j-1][parent[j-1][next]];
                rmq[j][next] = std::min (rmq[j-1][next], rmq[j-1][parent[j-1][next]]);
            }

            findParents (next);
        }
    }
}



int main(){

    int V, E, Q, P, root=1, src, dest, i, cost;
    fin >> V >> Q >> P;
    E = V - 1;
    for (i=2; i<=E+1; i++){
        fin >> src >> cost;
        dest = i;
        edge[src].push_back ({dest, cost});
        edge[dest].push_back ({dest, cost});
    }

    level[root] = 1;
    findParents (root);

    /*
    for (i=1; i<=V; i++)
        fout << parent[1][i] << '\n';
    */


    int node1, node2, A, B, C, D;
    std::vector < int > ans;
    fin >> node1 >> node2 >> A >> B >> C >> D;
    while (Q--){
        int answer;
        if (node1 == node2)
            answer = 0;
        else{
            int level1 = level[node1];
            int level2 = level[node2];
            int crt1 = node1;
            int crt2 = node2;
            if (level1 > level2){
                std::swap (level1, level2);
                std::swap (crt1, crt2);
            }

            int min = 1e9;
            int p = 15, diff = level2 - level1;
            while (level1 < level2){
                if ((1 << p) <= diff){
                    diff -= (1 << p);
                    min = std::min (min, rmq[p][crt2]);
                    level2 -= (1 << p);
                    crt2 = parent[p][crt2];
                }
                p --;
            }

            p = 15;
            int level = level1;
            while (parent[0][crt1] != parent[0][crt2]){
                if ((1 << p) < level and parent[p][crt1] != parent[p][crt2]){
                    min = std::min (min, rmq[p][crt1]);
                    min = std::min (min, rmq[p][crt2]);
                    crt1 = parent[p][crt1];
                    crt2 = parent[p][crt2];
                    level -= (1 << p);
                }
                p --;
            }
            min = std::min (min, std::min (rmq[0][crt1], rmq[0][crt2]));
            answer = min;
        }

        ans.push_back (answer);

        node1 = (node1 * A + node2 * B) % V + 1;
        node2 = (node2 * C + answer * D) % V + 1;
    }

    for (i=ans.size()-1; i>=ans.size()-P; i--)
        fout << ans[i] << '\n';


    return 0;
}