Cod sursa(job #2088448)

Utilizator giotoPopescu Ioan gioto Data 15 decembrie 2017 10:54:54
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>
using namespace std;

int n, m, p;
int a[32005], TT[32005], H[32005], c[20][32005], d[20][32005];
vector <pair <int, int> > v[32005];
inline void dfs(int nod, int lev){
    H[nod] = lev;
    for(auto it : v[nod]){
        if(it.first == TT[nod]) continue ;
        TT[it.first] = nod;
        c[0][it.first] = it.second;
        dfs(it.first, lev + 1);
    }
}
inline int lca(int x, int y){
    int ans = 2000000000;
    if(x == y) return 0;
    if(H[x] < H[y]) swap(x, y);
    int log1 = 0, log2 = 0;
    for(log1 = 1; (1 << log1) < H[x] ; ++log1) ;
    for(log2 = 1; (1 << log2) < H[y] ; ++log2) ;
    for(int k = log1; k >= 0 ; --k){
        if(H[x] - (1 << k) >= H[y]){
            ans = min(c[k][x], ans);
            x = d[k][x];
        }
    }
    if(x == y) return x;
    for(int k = log2; k >= 0 ; --k){
        if(d[k][x] && d[k][x] != d[k][y]){
            ans = min(c[k][x], ans);
            x = d[k][x];
            ans = min(c[k][y], ans);
            y = d[k][y];
        }
    }
    ans = min(c[0][x], ans);
    if(d[0][x] != y) ans = min(c[0][y], ans);
    return ans;
}
int main(){
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &p);
    int x, y;
    for(int i = 2; i <= n ; ++i) {
        scanf("%d%d", &x, &y);
        v[x].push_back(make_pair(i, y));
        v[i].push_back(make_pair(x, y));
    }
    dfs(1, 0);
    for(int i = 1; i <= n ; ++i) d[0][i] = TT[i];
    for(int k = 1; (1 << k) <= n ; ++k){
        for(int i = 1; i <= n ; ++i){
            d[k][i] = d[k - 1][d[k - 1][i]];
            c[k][i] = min(c[k - 1][i], c[k - 1][d[k - 1][i]]);
        }
    }
    int a, b, c, d;
    scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
    int nm = m - p;
    for(int i = 1; i <= nm ; ++i){
        int z = lca(x, y);
        x = (1LL * x * a + 1LL * y * b) % n + 1;
        y = (1LL * y * c + 1LL * z * d) % n + 1;
    }
    for(int i = 1; i <= p ; ++i){
        int z = lca(x, y);
        x = (1LL * x * a + 1LL * y * b) % n + 1;
        y = (1LL * y * c + 1LL * z * d) % n + 1;
        printf("%d\n", z);
    }
    return 0;
}