Cod sursa(job #3273584)

Utilizator solicasolica solica solica Data 2 februarie 2025 18:08:27
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
/*
  ____   ___  _     ___ ____    _
 / ___| / _ \| |   |_ _/ ___|  / \
 \___ \| | | | |    | | |     / _ \
  ___) | |_| | |___ | | |___ / ___ \
 |____/ \___/|_____|___\____/_/   \_\

*/
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long int
#define pii pair<int,int>

const int NMAX = 32e3+9;

const int MOD = 1e9+7;

const int LOG = 18;

const int INF = 1e9;

int binpow(int n, int k)
{
    if (k==0)
    {
        return 1;
    }
    int x=binpow(n,k/2)%MOD;
    if (k%2==0)
    {
        return x*x%MOD;
    }
    else
    {
        return x*x%MOD*n%MOD;
    }
}

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

#define cin fin
#define cout fout

int n,m,a,b,i,j,p,x,y,c,d,z;

int depth[NMAX];

pii parent[LOG][NMAX];

vector<pii>g[NMAX];

vector<pii>queries;

void dfs (int node, int parrent=0, int dep=0)
{
    depth[node]=dep;
    for (auto it : g[node])
    {
        if (it.first==parrent)
        {
            continue;
        }
        parent[0][it.first]={node,it.second};
        dfs (it.first,node,dep+1);
    }
}

void gen_sparse ()
{
    for (int i=1; i<LOG; i++)
    {
        for (int j=1; j<=n; j++)
        {
            parent[i][j].first=parent[i-1][parent[i-1][j].first].first;
            parent[i][j].second=min (parent[i-1][j].second,parent[i-1][parent[i-1][j].first].second);
        }
    }
}

int lca (int a, int b)
{
    int ans=INF;
    if (depth[a]<depth[b])
    {
        swap (a,b);
    }
    for (int i=LOG-1; i>=0; i--)
    {
        if (parent[i][a].first && depth[parent[i][a].first]>=depth[b])
        {
            ans=min (ans,parent[i][a].second);
            a=parent[i][a].first;
        }
    }
    if (a==b)
    {
        return ans;
    }
    for (int i=LOG-1; i>=0; i--)
    {
        if (parent[i][a].first && parent[i][a].first != parent[i][b].first)
        {
            ans=min (ans,parent[i][a].second);
            ans=min (ans,parent[i][b].second);
            a=parent[i][a].first,b=parent[i][b].first;
        }
    }
    ans=min (ans,min (parent[0][b].second,parent[0][a].second));
    return ans;
}

void run_case ()
{
    cin>>n>>m>>p;
    for (int i=2; i<=n; i++)
    {
        cin>>a>>b;
        g[a].pb ({i,b}),g[i].pb ({a,b});
    }
    dfs(1);
    gen_sparse();
    cin>>x>>y>>a>>b>>c>>d;
    for (i=1; i<=m; i++)
    {
        z=lca (x,y);
        if (m-i+1<=p)
        {
            cout<<z<<'\n';
        }
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL),cout.tie ();
    int teste;
    teste=1;
    while (teste--)
    {
        run_case();
    }
}