Cod sursa(job #3187898)

Utilizator divadddDavid Curca divaddd Data 31 decembrie 2023 03:11:01
Problema Atac Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int INF = 0x3f3f3f3f;
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;
        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);
    }
}

int query(int x, int y){
    if(x == y){
        return 0;
    }
    if(niv[x] < niv[y]){
        swap(x, y);
    }
    int diff = niv[x]-niv[y];
    int ans = INF;
    for(int i = LMAX-1; i >= 0; i--){
        if((diff>>i)&1){
            minSelf(ans, mn[i][x]);
            x = up[i][x];
        }
    }
    if(x == y){
        return ans;
    }
    for(int i = LMAX-1; i >= 0; i--){
        if(up[i][x] != up[i][y]){
            minSelf(ans, mn[i][x]);
            minSelf(ans, mn[i][y]);
            x = up[i][x];
            y = up[i][y];
        }
    }
    minSelf(ans, mn[0][x]);
    minSelf(ans, mn[0][y]);
    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});
    }
    memset(mn, INF, sizeof(mn));
    dfs(1);
    fin >> x >> y >> a >> b >> c >> d;
    for(int i = 1; i <= m; i++){
        int z = query(x, y);
        if(i >= m-p+1){
            fout << z << "\n";
        }
        x = (x*a + y*b)%n + 1;
        y = (y*c + z*c)%n + 1;
    }
    return 0;
}