Cod sursa(job #2840083)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 27 ianuarie 2022 09:01:18
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

long long a, b, c, d, nod1, nod2, n, m, p, depth[32005], ans, pow2;
vector <long long> G[32005];

struct smos {
    long long poz, val;
}s[20][32005];

void dfs(long long nod)
{
    depth[nod] = depth[s[1][nod].poz] + 1;
    for(long long vecin : G[nod])
        dfs(vecin);
}

void solve(long long x, long long y)
{
    if(depth[x] > depth[y])
        swap(x, y);
    //fout << x << ' ' << y << '\n';
    for(long long i = pow2; i > 0; i >>= 1)
    {
        if(depth[s[i][y].poz] >= depth[x])
        {
            ans = min(ans, s[i][y].val);
            y = s[i][y].poz;
        }
    }
    //fout << x << ' ' << y << '\n';
    if(x == y)
        return;
    for(long long i = pow2; i > 0; i >>= 1)
    {
        if(s[i][x].poz != s[i][y].poz)
        {
            ans = min(ans, s[i][x].val);
            ans = min(ans, s[i][y].val);
            x = s[i][x].poz;
            y = s[i][y].poz;
        }
    }
    //fout << x << ' ' << y << '\n';
    ans = min(ans, s[1][x].val);
    ans = min(ans, s[1][y].val);
}

int main()
{
    fin >> n >> m >> p;
    for(long long i = 2; i <= n; i++)
    {
        fin >> s[1][i].poz >> s[1][i].val;
        G[s[1][i].poz].push_back(i);
    }
    for(long long i = 2; (1 << (i - 1)) <= n; i++)
        for(long long nod = 1; nod <= n; nod++)
        {
            s[i][nod].poz = s[i - 1][s[i - 1][nod].poz].poz;
            s[i][nod].val = min(s[i - 1][nod].val, s[i - 1][s[i - 1][nod].poz].val);
        }
    dfs(1);
    fin >> nod1 >> nod2 >> a >> b >> c >> d;
    pow2 = 1;
    while((1 << (pow2 + 1)) <= n)
        pow2++;
    while(m--)
    {
        //fout << nod1 << ' ' << nod2 << '\n';
        ans = 0x3f3f3f3f;
        solve(nod1, nod2);
        //fout << nod1 << ' ' << nod2 << ' ' << ans << '\n' << '\n';
        if(ans == 0x3f3f3f3f)
            ans = 0;
        if(m < p)
            fout << ans << '\n';
        nod1 = (nod1 * a + nod2 * b) % n + 1;
        nod2 = (nod2 * c + ans * d) % n + 1;
    }
    return 0;
}