Cod sursa(job #2836363)

Utilizator DauCuDalta43Diaconu Razvan DauCuDalta43 Data 20 ianuarie 2022 11:03:34
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,m,p,P;
int a,b,c,d,x,y;
vector<pair<int,int> >h[33000];
int sol[500005],t;
int niv[33000],viz[33000],poz[65000],lg[65000],e[66000];
int rmq[20][65000];

void Citire()
{
    int i;
    fin>>n>>m>>P;
    for(i=2;i<=n;i++)
    {
        fin>>x>>y;
        h[i].push_back({x,y});
        h[x].push_back({i,y});
    }
    fin>>x>>y>>a>>b>>c>>d;
}

void DFS(int x)
{
    viz[x]=1;
    for(auto i:h[x])
        if(!viz[i.first])
    {
        niv[i.first]=niv[x]+1;
        DFS(i.first);
    }
}

void SkemaTovarasuluiEuler(int k)
{
    e[++p]=k;
    if(poz[k]==0)
        poz[k]=p;
    for(auto i:h[k])
        if(niv[i.first]==niv[k]+1)
        {
            SkemaTovarasuluiEuler(i.first);
            e[++p]=k;
        }
}

void MakeRMQ()
{
    int i,j;
    lg[1]=0;
    for(i=2;i<=p;i++)
        lg[i]=lg[i/2]+1;
    for(i=1;i<=p;i++)
        rmq[0][i]=e[i];
    for(i=1;(1<<i)<=p;i++)
        for(j=1;j+(1<<i)<=p;j++)
        {
            int len=(1<<(i-1));
            rmq[i][j]=rmq[i-1][j];
            if(niv[rmq[i-1][j+len]]<niv[rmq[i][j]])
                rmq[i][j]=rmq[i-1][j+len];
        }
}

int main()
{
    int i,s,vx,vy;
    Citire();
    niv[1]=1;
    DFS(1);
    SkemaTovarasuluiEuler(1);
    MakeRMQ();
    for(i=1;i<=P;i++)
    {
        int poz1=poz[x];
        int poz2=poz[y];
        if(poz1>poz2)
            swap(poz1,poz2);
        int expo=lg[poz2-poz1+1];
        int len=(1<<expo);
        int lca1=rmq[expo][x];
        int lca2=rmq[expo][y-len+1];
        if(niv[lca1]>niv[lca2])
            s=lca1;
        else s=lca2;
        sol[++t]=s;
        vx=x;
        vy=y;
        x=(vx*a+vy*b)%n+1;
        x=(vy*c+s*d)%n+1;
    }
    for(i=t-P+1;i<=t;i++)
        fout<<sol[i]<<"\n";
    return 0;
}