Cod sursa(job #2840149)

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

using namespace std;

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

const int inf = 0x3f3f3f3f;
int nod1, nod2, a, b, c, d, n, m, p, depth[32005], ans, log2;

struct smos {
    int poz, val;
}s[20][32005];
vector <int> G[32005];

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

void solve(int x, int y)
{
    if(depth[x] > depth[y])
        swap(x, y);
    //fout << x << ' ' << y << '\n';
    for(int i = log2; i >= 0; i--)
    {
        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(int i = log2; i >= 0; i--)
    {
        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[0][x].val);
    ans = min(ans, s[0][y].val);
}

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