Cod sursa(job #3037623)

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

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

const int NMAX=32010;
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(up[x][j]!=y) minbomb = min(minbomb, upmin[x][j]);
            else{
                int cx=x;
                for(int wow=j-1; wow>=0; wow--){
                    minbomb=min(minbomb, (upmin[cx][wow]==0 ? INT_MAX : upmin[cx][wow]));
                    cx=up[cx][wow];
                } 
            }
            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]==0 ? INT_MAX : upmin[x][j]));
            minbomb=min(minbomb, (upmin[y][j]==0 ? INT_MAX : 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;
    }
    upmin[1][0]=INT_MAX;
    up[1][0]=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';
    }
}