Cod sursa(job #2769229)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 14 august 2021 11:34:41
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 32005;
int n, m, p, dp[nmax][15][2], lev[nmax], x, y, a, b, c, d;
vector <pair <int, int> > G[nmax];

void dfs(int nod, int tata, int nivel){
    lev[nod] = nivel;
    for (auto it : G[nod]){
        if (it.first == tata){
            continue;
        }
        dp[it.first][0][0] = nod;
        dp[it.first][0][1] = it.second;
        dfs(it.first, nod, nivel + 1);
    }
}


int lca(int x, int y){
    if (lev[x] < lev[y]) swap(x, y);
    int minim = 1e9;
    if (lev[x] != lev[y]){
        for (int i = 14; i >= 0; --i){
            if (lev[x] - (1 << i) >= lev[y]){
                x = dp[x][i][0];
                minim = min(minim, dp[x][i][1]);
            }
        }
    }
    if (x == y){
        return minim;
    }
    for (int i = 14; i >= 0; --i){
        if (dp[x][i][0] != 0 && dp[y][i][0] != 0 && dp[x][i][0] != dp[y][i][0]){
            x = dp[x][i][0];
            y = dp[y][i][0];
            minim = min(minim, dp[x][i][1]);
            minim = min(minim, dp[y][i][1]);
        }
    }
    minim = min(minim, dp[x][0][1]);
    minim = min(minim, dp[y][0][1]);
    return minim;
}

int main(){
    fin >> n >> m >> p;
    for (int i = 2; i <= n; ++i){
        int u, v;
        fin >> u >> v;
        G[u].push_back({i, v});
        G[i].push_back({u, v});
    }
    dfs(1, 0, 0);
    for (int i = 1; (1 << i) <= n; ++i){
        for (int j = 1; j <= n; ++j){
            dp[j][i][0] = dp[dp[j][i - 1][0]][i - 1][0];
            dp[j][i][1] = min(dp[j][i - 1][1], dp[dp[j][i - 1][0]][i - 1][1]);
        }
    }
    fin >> x >> y >> a >> b >> c >> d;
    for (int i = 1; i <= m; ++i){
        int val = lca(x, y);
        if (x == y){
            val = 0;
        }
        if (i > m - p){
            fout << val << "\n";
        }
        x = (1LL * x * a + 1LL * y * b) % n + 1;
        y = (1LL * y * c + 1LL * val * d) % n + 1;
    }
    fin.close();
    fout.close();
    return 0;
}