Cod sursa(job #3042148)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 4 aprilie 2023 10:38:30
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <vector>
#include <cstring>
#define pi pair<int,int>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");


const int N = 32009, LG = 16, Inf = 0x3f3f3f3f;
int n,m,p,u,v,x,y,A,B,C,D;
vector<vector<pi> > G;
int dp[N][LG],t[N][LG],dep[N];

void Dfs(int x,int p)
{
    for(int i = 1; i < LG; ++i)
    {
        t[x][i] = t[t[x][i-1]][i-1];
        if(t[x][i])dp[x][i] = min(dp[x][i-1],dp[t[x][i-1]][i-1]);
    }

    for(auto aux : G[x])
    {
        int y = aux.first,
        w = aux.second;

        if(y == p)continue;

        t[y][0] = x;
        dp[y][0] = w;
        dep[y] = dep[x] + 1;

        Dfs(y,x);
    }
}

int query(int a,int b)
{
    int sol = 1e5 + 9;

    if(dep[a] < dep[b])
        swap(a,b);

    for(int i = LG - 1; i >= 0; --i)
        if(dep[t[a][i]] >= dep[b])
        {
            sol = min(sol,dp[a][i]);
            a = t[a][i];
        }

    if(a == b)return sol;

    for(int i = LG - 1; i >= 0; --i)
        if(t[a][i] && t[a][i] != t[b][i])
    {
        sol = min(sol,min(dp[a][i],dp[b][i]));
        a = t[a][i];
        b = t[b][i];
    }

    return min(sol,min(dp[a][0],dp[b][0]));
}

int main()
{
    memset(dp,Inf,sizeof(dp));
    cin>>n>>m>>p;
    G = vector<vector<pi>>(n+1);
    for(int i = 2; i <= n; ++i)
    {
        cin>>u>>v;
        G[u].push_back({i,v});
        G[i].push_back({u,v});
    }

    Dfs(1,0);

    cin>>x>>y>>A>>B>>C>>D;
    for(int i = 1; i <= m; ++i)
    {
        int Z = query(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;
}