Cod sursa(job #3187773)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 30 decembrie 2023 13:16:28
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <vector>
#define INF 0x3FFFFFFF
#define sz 32000

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

int n,m,q;

int A,B,C,D,X,Y;

vector <pair<int,int>> v[sz + 5];

int st[sz + 5];
int dr[sz + 5];
int p[16][sz + 5];
int val[16][sz + 5];
int o;

void dfs(int nod,int par,int mval)
{
    p[0][nod]=par;
    val[0][nod]=mval;
    st[nod]=++o;

    for(auto& i : v[nod])
        if(i.second!=par)
            dfs(i.second,nod,i.first);
    dr[nod]=++o;
}
bool is_ancestor(int anc,int x)
{
    return st[anc] <= st[x] && dr[x]<= dr[anc];
}
void proc()
{
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            p[j][i] = p[j-1][p[j-1][i]],val[j][i] = min(val[j-1][i],val[j-1][p[j-1][i]]);
}



int lca(int x,int y)
{
    if(x==y)
        return 0;
    int sol = INF;
    if(is_ancestor(x,y))
    {
        for(int i = 15;i>=0;i--)
            if(!is_ancestor(p[i][y],x))
                sol = min(sol,val[i][y]),y=p[i][y];
        return min(sol,val[0][y]);
    }
    if(is_ancestor(y,x))
    {
        swap(x,y);
        for(int i = 15;i>=0;i--)
            if(!is_ancestor(p[i][y],x))
                sol = min(sol,val[i][y]),y=p[i][y];
        return min(sol,val[0][y]);
    }
    int xc = x;
    for(int i =15;i>=0;i--)
    {
        int nod = p[i][xc];
        if(!is_ancestor(nod,y))
            xc=nod;
    }
    xc=p[0][xc];
    for(int i =15;i>=0;i--){
        if(!is_ancestor(p[i][x],xc))
            sol=min(sol,val[i][x]),x=p[i][x];
        if(!is_ancestor(p[i][y],xc))
            sol=min(sol,val[i][y]),y=p[i][y];
    }
    sol=min(sol,val[0][x]);
    sol=min(sol,val[0][y]);
    return sol;
}


int main()
{
    fin>>n>>m>>q;
    for(int i=2;i<=n;i++)
    {
        int x,z;
        fin>>x>>z;
        v[x].push_back({z,i});
        v[i].push_back({z,x});
    }
    fin>>X>>Y>>A>>B>>C>>D;
    dfs(1,0,0);
    dr[0]=++o;
    proc();
    for(int i =1 ; i<=m;i++)
    {
        int Z = lca(X,Y);
        if(i>m-q)
            fout<<Z<<'\n';
        X=(X*A + Y*B)%n + 1;
        Y=(Y*C + Z*D)%n + 1;
    }
}