Cod sursa(job #2605413)

Utilizator Rares31100Popa Rares Rares31100 Data 24 aprilie 2020 21:16:14
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>
#define ULL unsigned long long
#define Inf 1000000007

using namespace std;

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

int n,Q,P;
int vf[64001],urm[64001],cost[64001],last[32001],nr;
int euler[64001],nivEu[64001],pozitie[32001],Nivel[32001],t;
int rmq[16][64001];
int stram[15][32001],minim[15][32001];
int x,y,z;
ULL A,B,C,D;

void adauga(int nod,int vec,int ct)
{
    vf[++nr]=vec;
    urm[nr]=last[nod];
    last[nod]=nr;
    cost[nr]=ct;
}

void citire()
{
    in>>n>>Q>>P;

    for(int i=2,j,ct;i<=n;i++)
    {
        in>>j>>ct;
        adauga(i,j,ct);
        adauga(j,i,ct);
    }

    in>>x>>y>>A>>B>>C>>D;
}

void dfs(int nod=1,int from=0,int nivel=1)
{
    euler[++t]=nod;
    nivEu[t]=nivel;
    pozitie[nod]=t;

    stram[0][nod]=from;
    Nivel[nod] = nivel;

    for(int k=last[nod];k;k=urm[k])
        if(vf[k]!=from)
        {
            dfs(vf[k],nod,nivel+1);
            euler[++t]=nod;
            nivEu[t]=nivel;

            minim[0][vf[k]]=cost[k];
        }
}

void rmqBuild()
{
    int maxim = 2*n-1;
    int rMax = log2(maxim);

    for(int i=1; i<=maxim; i++)
        rmq[0][i] = i;

    for(int r=1,l=1; r<=rMax; r++,l*=2)
        for(int i=1;i<= maxim-2*l+1;i++)
            if( nivEu[ rmq[r-1][i] ] < nivEu[ rmq[r-1][i+l] ] )
                rmq[r][i]=rmq[r-1][i];
            else
                rmq[r][i]=rmq[r-1][i+l];
}

void stramosBuild()
{
    minim[0][1]=Inf;

    int rMax=log2(n);

    for(int r=1;r<=rMax;r++)
        for(int i=1;i<=n;i++)
        {
            stram[r][i] = stram[r-1][ stram[r-1][i] ];
            minim[r][i] = min( minim[r-1][i], minim[r-1][ stram[r-1][i] ] );
        }
}

int lca(int x,int y)
{
    int st = pozitie[x];
    int dr = pozitie[y];

    if(st>dr)
        swap(st,dr);

    int r = log2( dr-st+1 );
    if( nivEu[ rmq[r][st] ] < nivEu[ rmq[r][dr-(1<<r)+1] ] )
        return euler[ rmq[r][st] ];
    else
        return euler[ rmq[r][dr-(1<<r)+1] ];
}

int distMin(int nod,int dest)
{
    int Minim = Inf;
    int Dist = Nivel[nod] - Nivel[dest];

    for( int j=0; (1<<j)<=Dist; j++)
        if( (1<<j)&Dist )
        {
            Minim = min(Minim, minim[j][nod] );
            nod = stram[j][nod];
        }

    return Minim;
}

int main()
{
    citire();
    dfs();
    rmqBuild();
    stramosBuild();

    for( int k=1;k<=Q;k++ )
    {
        int p = lca(x,y);

        if(x!=y)
            z = min( distMin(x,p) , distMin(y,p) );
        else
            z = 0;

        x = ( A*x + B*y ) % n +1;
        y = ( C*y + D*z ) % n +1;

        if(k>Q-P)
            out<<z<<'\n';
    }

    return 0;
}