Cod sursa(job #3237887)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 14 iulie 2024 00:58:21
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define vi vector<int>
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define pb push_back
//#define int long long
#define ll long long

using namespace std;
const string TASK("atac");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

const int N = 50009, Inf = 0x3f3f3f3f;

int n, m, p, X, Y, A, B, C, D;
vvi G(N);

int dep[N], t[N], ct[N], j[N], cj[N];
void Dfs(int x = 1, int p = 0)
{
    dep[x] = dep[p] + 1;

    if(dep[t[x]] - dep[j[t[x]]] == dep[j[t[x]]] - dep[j[j[t[x]]]])
    {
        cj[x] = min({ct[x], cj[t[x]], cj[j[t[x]]]});
        j[x] = j[j[t[x]]];
    }
    else
    {
        cj[x] = ct[x];
        j[x] = t[x];
    }

    for(auto y : G[x])
        Dfs(y, x);
}

int solve(int x, int y)
{
    if(x == y)return 0;

    int mn = Inf;
    if(dep[x] < dep[y])swap(x, y);

    while(dep[x] > dep[y])
        if(dep[j[x]] >= dep[y])
        {
            mn = min(mn, cj[x]);
            x = j[x];
        }
        else
        {
            mn = min(mn, ct[x]);
            x = t[x];
        }

    while(x != y)
        if(j[x] != j[y])
        {
            mn = min({mn, cj[x], cj[y]});
            x = j[x];
            y = j[y];
        }
        else
        {
            mn = min({mn, ct[x], ct[y]});
            x = t[x];
            y = t[y];
        }

    return mn;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> p;

    int f, v;
    ct[1] = cj[1] = Inf;
    FOR(i, 2, n)
    {
        cin >> f >> v;
        G[f].pb(i);

        t[i] = f;
        ct[i] = v;
    }

    Dfs();

    cin >> X >> Y >> A >> B >> C >> D;

    int Z;
    FOR(i, 1, m)
    {
        Z = solve(X, Y);

        if(i >= m - p + 1)cout << Z << '\n';

        X = (X * A + Y * B) % n + 1;
        Y = (Y * C + Z * D) % n + 1;
    }
    return 0;
}