Cod sursa(job #3186720)

Utilizator divadddDavid Curca divaddd Data 24 decembrie 2023 20:04:40
Problema Atac Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int LMAX = 17;
const int NMAX = 4e4+2;
int n,m,p,x,y,a,b,c,d,niv[NMAX],up[LMAX][NMAX],mn[LMAX][NMAX];
vector<pii> v[NMAX];

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

void minSelf(auto &a, auto b){
    a = min(a, b);
}

void dfs(int nod, int tata = -1){
    for(auto [fiu, cost]: v[nod]){
        if(fiu == tata){
            continue;
        }
        niv[fiu] = 1+niv[nod];
        mn[0][fiu] = cost;
        up[0][fiu] = nod;
        //cout << "up[0][" << fiu << "] = " << nod << "\n";
        for(int i = 1; i < LMAX; i++){
            mn[i][fiu] = mn[i-1][fiu];
            up[i][fiu] = up[i-1][up[i-1][fiu]];
            minSelf(mn[i][fiu], mn[i-1][up[i-1][fiu]]);
        }
        dfs(fiu, nod);
    }
}

pii kth(int x, int k){
    int ans = LLONG_MAX;
    for(int i = LMAX-1; i >= 0; i--){
        if((k>>i)&1){
            //cout << i << " = " << mn[i][x] << "\n";
            minSelf(ans, mn[i][x]);
            x = up[i][x];
        }
    }
    return {x, ans};
}

int query(int x, int y){
    if(x == y){
        return 0;
    }
    if(niv[x] > niv[y]){
        swap(x, y);
    }
    int xcpy = x, ycpy = y;
    //cout << x << ", " << y << "\n";
    //cout << niv[x] << ", " << niv[y] << "\n";
    int diff = niv[y]-niv[x];
    //cout << "kth(" << y << ", " << diff << ") = ";
    y = kth(y, diff).first;
    //cout << y << "\n";
    int lca = 0;
    int ans = 0;
    if(x != y){
        for(int i = LMAX-1; i >= 0; i--){
            if(up[i][x] != up[i][y]){
                x = up[i][x];
                y = up[i][y];
            }
        }
        lca = up[0][x];
        tie(x, y) = (pii){xcpy, ycpy};
        ans = min(kth(x, niv[x]-niv[lca]).second, kth(y, niv[y]-niv[lca]).second);
    }else{
        lca = x;
        tie(x, y) = (pii){xcpy, ycpy};
        //cout << "x era tatic\n";
        //cout << "kth(" << y << ", " << niv[y]-niv[lca] << ") .\n";
        ans = kth(y, niv[y]-niv[lca]).second;
    }
    //cout << "lca(" << xcpy << ", " << ycpy << ") = " << lca << "\n";
    //cout << "ans = " << ans << "\n";
    return ans;
}

signed main()
{
    fin >> n >> m >> p;
    for(int i = 2; i <= n; i++){
        int u,val;
        fin >> u >> val;
        v[u].push_back({i, val});
        v[i].push_back({u, val});
    }
    for(int i = 0; i < LMAX; i++){
        mn[i][1] = INT_MAX;
    }
    dfs(1);
    int ans = 0;
    fin >> x >> y >> a >> b >> c >> d;
    for(int i = 1; i <= m; i++){
        int z = query(x, y);
        //cout << x << ", " << y << " = " << z << " ....\n";
        if(i >= m-p+1){
            fout << z << "\n";
        }
        int xprev = x, yprev = y;
        x = (xprev*a + yprev*b)%n + 1;
        y = (yprev*c + z*c)%n + 1;
    }
    return 0;
}