Cod sursa(job #2488891)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 7 noiembrie 2019 19:33:06
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int nmax = 32000, lgmax = 17, inf = 0x3f3f3f3f;

struct Street{
    int nod, cost;
};
vector <Street> g[nmax + 5];
int n, m, p, A, B, C, D, X, Y, level[nmax + 5], a[lgmax][nmax + 5], c[lgmax][nmax + 5], log2[nmax + 5];

void Read(){
    fin >> n >> m >> p;
    for (int i = 2; i <= n; i++){
        int x, y;
        fin >> x >> y;
        g[i].push_back({x, y});
        g[x].push_back({i, y});
    }
    fin >> X >> Y >> A >> B >> C >> D;
}

void DFS(int nod, int tata){
    level[nod] = level[tata] + 1;
    a[0][nod] = tata;
    for (auto i : g[nod])
        if (i.nod != tata){
            DFS(i.nod, nod);
            c[0][i.nod] = i.cost;
        }
}

void Precalc(){
    DFS(1, 0);
    for (int i = 2; i <= n; i++)
        log2[i] = log2[i / 2] + 1;
    for (int i = 1; i <= log2[n]; i++)
        for (int j = 1; j <= n; j++){
            a[i][j] = a[i - 1][a[i - 1][j]];
            c[i][j] = min(c[i - 1][j], c[i - 1][c[i - 1][j]]);
        }
}

int Min(int x, int y){
    if (x == y)
        return 0;
    int sol = inf;
    if (level[x] > level[y])
        swap(x, y);
    while (level[x] < level[y]){
        int dif = level[y] - level[x];
        sol = min(sol, c[log2[dif]][y]);
        y = a[log2[dif]][y];
    }
    if (x == y)
        return sol;
    for (int i = log2[level[x]]; i >= 0; i--)
        if (a[i][x] != a[i][y]){
            sol = min(sol, c[i][x]);
            x = a[i][x];
            sol = min(sol, c[i][y]);
            y = a[i][y];
        }
    sol = min(sol, c[0][x]);
    sol = min(sol, c[0][y]);
    return sol;
}

int main(){
    Read();
    Precalc();
    for (int i = 1; i <= m; i++){
        int Z = Min(X, Y);
        if (X == Y)
            Z = 0;
        if (i > m - p)
            fout << Z << '\n';
        int X1, Y1;
        X1 = (X * A + Y * B) % n + 1;
        Y1 = (Y * C + Z * D) % n + 1;
        X = X1;
        Y = Y1;
    }
    return 0;
}