Cod sursa(job #2604707)

Utilizator sichetpaulSichet Paul sichetpaul Data 23 aprilie 2020 12:21:31
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>
#define Nmax 32005
#define LG 18
#define INF 1e9
#define ll long long
using namespace std;

ifstream f("atac.in");
ofstream g("atac.out");

int N, K, Q, P, A, B, C, D, X, Y, L;
int lev[Nmax], le[Nmax], ri[Nmax], anc[Nmax][LG], dp[Nmax][LG];
vector<pair<int, int> > G[Nmax];

bool isAnc(int x, int y) {
    return (le[x] <= le[y] && ri[y] <= ri[x]);
}
int lca(int x, int y) {
    if (isAnc(x, y)) return x;
    if (isAnc(y, x)) return y;
    for (int i = L; i >= 0; --i)
        if (!isAnc(anc[x][i], y)) x = anc[x][i];
    return anc[x][0];
}
int calc(int x, int root) {
    int ans = INF;
    for (int i = L; i >= 0 && x != root; --i) {
        int nxt = anc[x][i];
        if (lev[nxt] < lev[root]) continue;
        ans = min(ans, dp[x][i]);
        x = nxt;
    }
    return ans;
}

void DFS(int node, int father, int len) {
   lev[node] = lev[father] + 1;
   le[node] = ++K;
   anc[node][0] = father;
   dp[node][0] = len;

   for (int i = 1; i <= L; ++i) {
       int mid = anc[node][i - 1];
       anc[node][i] = anc[mid][i - 1];
       dp[node][i] = min(dp[node][i - 1], dp[mid][i - 1]);
   }

   for (auto it: G[node])
     if (it.first != father) DFS(it.first, node, it.second);
   ri[node] = ++K;
}
int main()
{
    f >> N >> Q >> P;
    L = ceil(log2(N));
    for (int i = 2; i <= N; ++i) {
        int x, y;
        f >> x >> y;
        G[x].push_back({i, y});
        G[i].push_back({x, y});
    }
    DFS(1, 1, INF);

    f >> X >> Y >> A >> B >> C >> D;
    for (int q = Q; q >= 1; --q) {
        int Lca = lca(X, Y);
        int ans = min(calc(X, Lca), calc(Y, Lca));
        if (X == Y) ans = 0;
        if (q <= P) g << ans << '\n';

        int XP = (1ll * X * A + 1ll * Y * B) % N + 1;
        int YP = (1ll * Y * C + 1ll * ans * D) % N + 1;
        X = XP, Y = YP;
    }

    return 0;
}