Cod sursa(job #2890735)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 16 aprilie 2022 14:01:05
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb
//Ilie Dumitru
#include<cstdio>
#include<vector>
typedef long long int ll;
const int NMAX=32005, BITMAX=16;
const ll MOD=1000000007;

FILE* f=fopen("atac.in", "r"), *g=fopen("atac.out", "w");
int N, M, P;
int depth[NMAX], TTie[BITMAX][NMAX], min[BITMAX][NMAX];
struct edge
{
    int node, w;
};
std::vector<edge> gr[NMAX];

void buildLCA()
{
    int i, j;
    for(j=1;j<BITMAX;++j)
    {
        for(i=1;i<=N;++i)
        {
            if(min[j-1][i]<min[j-1][TTie[j-1][i]])
                min[j][i]=min[j-1][i];
            else
                min[j][i]=min[j-1][TTie[j-1][i]];
            TTie[j][i]=TTie[j-1][TTie[j-1][i]];
        }
    }
}

void dfs(int node, int tt, int dpth)
{
    std::vector<edge>::iterator i0, i1;
    depth[node]=dpth;
    TTie[0][node]=tt;
    for(i0=gr[node].begin(), i1=gr[node].end();i0!=i1;++i0)
        if(i0->node!=tt)
        {
            min[0][i0->node]=i0->w;
            dfs(i0->node, node, dpth+1);
        }
}

int query(int a, int b)
{
    if(a==b)
        return 0;
    if(depth[a]>depth[b])
    {
        int aux=a;
        a=b;
        b=aux;
    }
    int val=MOD, i;
    int dpthDiff=depth[b]-depth[a];
    for(i=0;i<BITMAX && dpthDiff>=(1<<i);++i)
        if(dpthDiff&(1<<i))
        {
            if(min[i][b]<val)
                val=min[i][b];
            b=TTie[i][b];
        }
    if(a==b)
        return val;
    for(i=BITMAX-1;i>-1;--i)
    {
        if(TTie[i][a]!=TTie[i][b])
        {
            if(min[i][a]<val)
                val=min[i][a];
            if(min[i][b]<val)
                val=min[i][b];
            a=TTie[i][a];
            b=TTie[i][b];
        }
    }
    if(min[0][a]<val)
        val=min[0][a];
    if(min[0][b]<val)
        val=min[0][b];
    return val;
}

int main()
{
    int i, x, y, X, Y, A, B, C, D;
    fscanf(f, "%d%d%d", &N, &M, &P);
    for(i=2;i<=N;++i)
    {
        fscanf(f, "%d%d", &x, &y);
        gr[i].push_back({x, y});
        gr[x].push_back({i, y});
    }
    fscanf(f, "%d%d%d%d%d%d", &X, &Y, &A, &B, &C, &D);
    min[0][1]=MOD;
    dfs(1, 1, 0);
    buildLCA();
    while(M>P)
    {
        x=query(X, Y);
        X=(X*A+Y*B)%N+1;
        Y=(Y*C+x*D)%N+1;
        --M;
    }
    while(M)
    {
        x=query(X, Y);
        //printf("x:%d\ny:%d\nc:%d\n\n", X, Y, x);
        X=(X*A+Y*B)%N+1;
        Y=(Y*C+x*D)%N+1;
        fprintf(g, "%d\n", x);
        --M;
    }
    fclose(f);
    fclose(g);
    return 0;
}