Cod sursa(job #2859231)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 1 martie 2022 00:44:06
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>
using namespace std;

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

const int dim=33000,Log=16,inf=1e9;

struct elem{
    int x,c;
};

vector<elem>v[dim];

int depth[dim];
int up[dim][Log],rmq[dim][Log];

void dfs(int x,int tata){
    depth[x]=depth[tata]+1;
    for(int i=1;i<Log;i++){
        up[x][i]=up[up[x][i-1]][i-1];
    }
    for(int i=1;i<Log;i++){
        rmq[x][i]=min(rmq[x][i-1],rmq[up[x][i-1]][i-1]);
    }
    for(elem it:v[x]){
        int y=it.x,c=it.c;
        if(y!=tata){
            up[y][0]=x;
            rmq[y][0]=c;
            dfs(y,x);
        }
    }
}

int query(int x,int y){
    if(x==y){
        return 0;
    }
    if(depth[x]<depth[y]){
        swap(x,y);
    }
    int diferenta=depth[x]-depth[y];
    int ans=inf;
    for(int i=Log-1;i>=0;i--){
        if(diferenta&(1<<i)){
            ans=min(ans,rmq[x][i]);
            x=up[x][i];
        }
    }
    if(x==y){
        return ans;
    }
    for(int i=Log-1;i>=0;i--){
        if(up[x][i]!=up[y][i]){
            ans=min(ans,rmq[x][i]);
            ans=min(ans,rmq[y][i]);
            x=up[x][i];
            y=up[y][i];
        }
    }
    ans=min(ans,min(rmq[x][0],rmq[y][0]));
    return ans;
}

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