Cod sursa(job #3037634)

Utilizator begusMihnea begus Data 25 martie 2023 23:24:35
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=32001;
const int LOG=20;

vector<int> children[NMAX];
int n, m, p, x, y, a, b, c, d, up[NMAX][LOG], upmin[NMAX][LOG], depth[NMAX];

void dfs(int s){
    for(auto u : children[s]){
        depth[u]=depth[s]+1;
        up[u][0]=s;
        for(int j=1; j<LOG; j++){
            up[u][j]=up[up[u][j-1]][j-1];
            upmin[u][j]=min(upmin[u][j-1], upmin[up[u][j-1]][j-1]);
        }
        dfs(u);
    }
}

int lca(int x, int y){
    if(x==y) return 0;
    int minbomb=INT_MAX;
    if(depth[x]<depth[y]) swap(x, y);
    int k=depth[x]-depth[y];
    for(int j=LOG-1; j>=0; j--){
        if(k & (1<<j)){
            if(x!=y) minbomb = min(minbomb, upmin[x][j]);
            x=up[x][j];
        }
            
    }
    if(x==y) return minbomb;
    for(int j=LOG-1; j>=0; j--){
        if(up[x][j]!=up[y][j]){
            minbomb=min(minbomb, upmin[x][j]);
            minbomb=min(minbomb, upmin[y][j]);
            x=up[x][j];
            y=up[y][j];
        }
    }
    return min(minbomb, min(upmin[x][0], upmin[y][0]));
}

int main(){
    fin >> n >> m >> p;
    for(int i=2; i<=n; i++){
        int x, y;
        fin >> x >> y;
        children[min(i, x)].push_back(max(i, x));
        upmin[i][0]=y;
    }
    for(int j=0; j<LOG; j++){
        upmin[1][j]=INT_MAX;
        up[1][j]=1;
    }
    fin >> x >> y >> a >> b >> c >> d;
    dfs(1);

    while(m--){
        int minbomb = lca(x, y);
        x=(x*a+y*b)%n+1;
        y=(y*c+minbomb*d)%n+1;
        if(m<p) fout << minbomb <<  '\n';
    }
}