Cod sursa(job #2973186)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 31 ianuarie 2023 10:28:30
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define INF 0x3f3f3f3f
const int NMAX = 32005;
const int MMAX = 500005;
const int EMAX = NMAX * 3;
const int LMAX =  20;
int a, b, c, d, z, x, y;
int n, m, u, v, p;
int rmq[LMAX][NMAX], h[NMAX], t[LMAX][NMAX];
vector<int> G[NMAX];

void dfs(int nod, int tata)
{
    h[nod] = tata;
    for (auto it : G[nod])
        dfs(it, tata+1);
}

void RMQ()
{
    for (int e=1;(1<<e) <=n;e++){
        for (int i=1;i<=n;i++){
            t[e][i] = t[e-1][t[e-1][i]];
            rmq[e][i] = min(rmq[e-1][i], rmq[e-1][t[e-1][i]]);
        }
    }
}

int lca(int x, int y)
{
    int kon = INF;
    if (h[x] < h[y])
        swap(x, y);
    int level = h[x] - h[y];
    for (int e=0;e<=15;e++){
        if (level & (1<<e))
            kon = min(kon, rmq[e][x]), x = t[e][x];
    }

    for (int e=15;e>=0;e--){
        if (t[e][x] != t[e][y]){
            kon = min(kon, rmq[e][x]);
            kon = min(kon, rmq[e][y]);
            x = t[e][x];
            y = t[e][y];
        }
    }

    if (x != y){
        kon = min(kon, rmq[0][x]);
        kon = min(kon, rmq[0][y]);
    }
    return kon;
}

int main()
{
    fin >> n >> m >> p;
    for (int i=2;i<=n;i++){
        fin >> u >> v;
        G[u].push_back(i);
        rmq[0][i] = v;  
        t[0][i] = u;
    }
    dfs(1, 0);
    RMQ();
    fin >> x >> y >> a >> b >> c >> d;
    for (int i=1;i<=m;i++){
        if (x == y){
            z = 0;
        }else{
            z = lca(x, y);
            if (i > m-p)
                fout << z << '\n';
            x = (x * a + y * b) % n + 1;
            y = (y * c + z * d) % n + 1;
        }
    }
    return 0;
}