Cod sursa(job #2644105)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 23 august 2020 14:12:52
Problema Atac Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;

int n,m,p, cst[NMAX], h[NMAX],y,c,x,a,b,d;
pair<int, int> T[20][NMAX];
vector<int> v[NMAX];

void dfs(int nod, int H = 1){
    h[nod] = H;
    for (auto it : v[nod]){
        dfs(it, H+1);
    }
}

int query(int x, int y){
    if (x == y) return 0;
    int ans = 1e9;
    if (h[x] > h[y]) swap(x,y);
    for (int i=19;i>=0;i--)
        if (h[y] - (1<<i) >= h[x]){
            ans = min(ans, T[i][y].second);
            y = T[i][y].first;
        }

    for (int i=19;i>=0;i--){
        if (T[i][x].first != T[i][y].first){
            ans = min({ans, T[i][x].second, T[i][y].second});
            x = T[i][x].first;
            y = T[i][y].first;
        }
    }
    if (x!=y){
        ans = min({ans, T[0][x].second, T[0][y].second});
    }
    return ans;
}

int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    cin.sync_with_stdio(false);
    cin >> n >> m >> p;
    for (int i=2;i<=n;i++){
        cin >> y >> c;
        T[0][i] = {y,c};
        v[y].push_back(i);
    }
    dfs(1);

    for (int k=1;k<20;k++){
        for (int i=1;i<=n;i++){
            T[k][i] = {T[k-1][T[k-1][i].first].first, min(T[k-1][i].second, T[k-1][T[k-1][i].first].second)};
        }
    }

    cin >> x >> y >> a >> b >> c >> d;

    int ans;
    for (int i=1;i<=m;i++){
        if (i >= 2){
            x = (1LL * x * a + 1LL * y * b) % n + 1;
            y = (1LL * y * c + 1LL * ans * d) % n + 1;
        }

        ans = query(x,y);

        if (i + p > m){
            cout << ans << '\n';
        }
    }

    return 0;
}