Cod sursa(job #3142152)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 19 iulie 2023 16:14:59
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

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

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

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

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 = 1e9;
    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]=1e9;
        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';
    }
    return 0;
}