Cod sursa(job #2436113)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 4 iulie 2019 16:29:01
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int N = 32005;
const int L = 20;
vector<pair<int,int> >v[N];
int lvl[N],dp[L][N],cost[L][N];
void dfs(int x)
{
    for (auto it: v[x])
        if (!lvl[it.first])
        {
            lvl[it.first] = 1+lvl[x];
            dp[0][it.first] = x;
            cost[0][it.first] = it.second;
            dfs(it.first);
        }
}
int query(int x, int y)
{
    if (lvl[x]<lvl[y])
        swap(x,y);
    int L1 = 1, L2 = 1;
    while ((1<<L1)<lvl[x])
        L1++;
    while ((1<<L2)<lvl[y])
        L2++;
    int ans = INT_MAX;
    for (int i = L1; i>=0; i--)
        if (lvl[x]-(1<<i)>=lvl[y])
        {
            ans = min(ans,cost[i][x]);
            x = dp[i][x];
        }
    for (int i = L2; i>=0; i--)
        if (lvl[x]-(1<<i)>=0 && dp[i][x]!=dp[i][y])
        {
            ans = min(ans,min(cost[i][x],cost[i][y]));
            x = dp[i][x];
            y = dp[i][y];
        }
    if (x!=y)
        ans = min(ans,min(cost[0][x],cost[0][y]));
    if (ans == INT_MAX)
        ans = 0;
    return ans;
}
int main()
{
    int n,m,p;
    in >> n >> m >> p;
    for (int i = 2; i<=n; i++)
    {
        int x,y;
        in >> x >> y;
        v[x].push_back({i,y});
        v[i].push_back({x,y});
    }
    int x,y,a,b,c,d;
    in >> x >> y >> a >> b >> c >> d;
    lvl[1] = 1;
    dfs(1);
    for (int i = 1; (1<<i)<=n; i++)
        for (int j = 1; j<=n; j++)
        {
            dp[i][j] = dp[i-1][dp[i-1][j]];
            cost[i][j] = min(cost[i-1][j],cost[i-1][dp[i-1][j]]);
        }
    for (int i = 1; i<=m; i++)
    {
        int z = query(x,y);
        if (i>=m-p+1)
            out << z << "\n";
        x = (x*a+y*b)%n+1;
        y = (y*c+z*d)%n+1;
    }
}