Cod sursa(job #2329755)

Utilizator DimaTCDima Trubca DimaTC Data 27 ianuarie 2019 13:27:19
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<bits/stdc++.h>
#define N 32005
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

int n, e;
int LOG[2*N], F[N], L[2*N], E[2*N];
int viz[2*N];
int dp[N][20], mn[N][20];
int rmq[2*N][20];
vector<pii>V[N];
int m,p;

void DFS(int x, int h) {
    E[++e]=x;
    L[e]=h;
    F[x]=e;
    viz[x]=1;
    for (auto it:V[x]) {
        if (!viz[it.fi]) {
            DFS(it.fi, h+1);
            dp[it.fi][0]=x;
            mn[it.fi][0]=it.se;
            L[++e]=h;
            E[e]=x;
        }
    }
}
int rs;

int LCA(int a, int b) {
    a=F[a], b=F[b];
    if (a>b) swap(a,b);
    int k=LOG[b-a+1];
    if (L[rmq[a][k]]<L[rmq[b-(1<<k)+1][k]]) return E[rmq[a][k]];
    else return E[rmq[b-(1<<k)+1][k]];
}

int solve(int x, int p) {
    int k=L[F[x]]-L[F[p]];
    int nod=x, rs=1e9;
    for (int i=0; i<=16; ++i) {
        if ((1<<i) & k) {
            rs=min(rs, mn[nod][i]);
            nod=dp[nod][i];
        }
    }
    return rs;
}

int main() {
    ifstream cin("atac.in");
    ofstream cout("atac.out");
    cin>>n>>m>>p;
    for (int i=2; i<=n; ++i) {
        int x,y; cin>>x>>y;
        V[x].push_back({i,y});
        V[i].push_back({x,y});
    }

    for (int i=2; i<=2*N-5; ++i) LOG[i]=LOG[i>>1]+1;
    DFS(1,0);

    for (int i=1; i<=e; ++i) rmq[i][0]=i;
    for (int j=1; (1<<j)<=e; ++j) {
        for (int i=1; i+(1<<j)-1<=e; ++i) {
            if (L[rmq[i][j-1]]<L[rmq[i+(1<<(j-1))][j-1]]) rmq[i][j]=rmq[i][j-1];
            else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
        }
    }

    for (int j=1; (1<<j)<=n; ++j) {
        for (int i=1; i<=n; ++i) {
            dp[i][j]=dp[dp[i][j-1]][j-1];
            mn[i][j]=min(mn[i][j-1], mn[dp[i][j-1]][j-1]);
        }
    }

    int X,Y,A,B,C,D,Z;
    cin>>X>>Y>>A>>B>>C>>D;
    for (int i=1; i<=m; ++i) {
        int lca=LCA(X,Y);
        if (X==Y) rs=0;
        else rs=min(solve(X, lca), solve(Y, lca));
        Z=rs;
        X=(X*A+Y*B)%n+1;
        Y=(Y*C+Z*D)%n+1;
        if (m-i+1<=p) cout<<rs<<'\n';
    }

    return 0;
}