Cod sursa(job #2988814)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 5 martie 2023 15:08:39
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define nmax 32005
#define pmax 500005
vector<pair<int,int> > g[nmax];
int parc[3*nmax],h[3*nmax],frst[nmax];
int viz[nmax];
int minim[3*nmax][70];
int nr=0;
int n;
int inaltime[nmax];

void dfs(int nod,int nivel)
{
    parc[++nr]=nod;
    h[nr]=nivel;
    inaltime[nod]=nivel;
    frst[nod]=nr;
    viz[nod]=1;

    for(int i=0; i<g[nod].size(); i++)
    {
        int s=g[nod][i].first;
        if(!viz[s])
        {
            dfs(s,nivel+1);
            parc[++nr]=nod;
            h[nr]=nivel;
        }
    }
}
void rmq()
{
    for(int i=1; i<=nr; i++)minim[i][0]=i;
    for(int l=1; (1<<l)<=nr; l++)
    {
        int   pp=1<<l;
        pp=pp/2;

        for(int i=1; i+pp<=nr; i++)
        {
            if(h[minim[i][l-1]]<=h[minim[i+pp+1][l-1]])
            {
                minim[i][l]=minim[i][l-1];
            }
            else
            {
                minim[i][l]=minim[i+pp+1][l-1];

            }
        }
    }
}
int rezultat;
int altdfs(int nod,int stramos)
{
    if(nod ==stramos) return rezultat;
    for(int i=0; i<g[nod].size(); i++)
    {
        int s=g[nod][i].first;
        if(inaltime[s]<inaltime[nod]&&inaltime[s]>=inaltime[stramos])
        {
            rezultat=min(rezultat,g[nod][i].second);
            altdfs(s,stramos);
        }
    }
}
int vezi(int x, int y)
{
    if(frst[x]>frst[y])swap(x,y);
    int l=abs(frst[x]-frst[y]);
    l=log2(l);
    int stramos;
    if(h[minim[frst[x]][l]]<h[minim[frst[y]-(1<<l)+1][l]])
    {
        stramos=parc[minim[frst[x]][l]];
    }
    else
    {
        stramos=parc[minim[frst[y]-(1<<l)+1][l]];
    }
    rezultat=INT_MAX;
    altdfs(y,stramos);
    int aux=rezultat;
    rezultat=INT_MAX;
    altdfs(x,stramos);
    return min(rezultat,aux);

}
int main()
{
    int m,p,i,u,v,x,y,a,b,c,d;
    fin>>n>>m>>p;
    for(i=2; i<=n; i++)
    {
        fin>>u>>v;
        g[i].push_back({u,v});
        g[u].push_back({i,v});
    }
    fin>>x>>y>>a>>b>>c>>d;
    frst[1]=1;
    dfs(1,1);
    rmq();
    for(i=1; i<=m-p; i++)
    {
        int z=vezi(x,y);
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    for(i=m-p+1; i<=m; i++)
    {
        int z=vezi(x,y);
        fout<<z<<'\n';
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    return 0;
}