Cod sursa(job #2456180)

Utilizator refugiatBoni Daniel Stefan refugiat Data 13 septembrie 2019 20:10:41
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream si("atac.in");
ofstream so("atac.out");

const int NMax = 32050;
const int LMax = 20;

int lvl[NMax];
pair<int, int> lift[LMax][NMax];
vector<vector<pair<int, int>>> g;

void dfs(int node, int father, int cost) {
    for(auto x: g[node]) {
        if(x.first==father)
            continue;
        lvl[x.first]=lvl[node]+1;
        dfs(x.first, node, x.second);
    }
    lift[0][node]={father, cost};
}

int lca(int x, int y) {
    if(x==y)
        return 0;
    if(lvl[x]<lvl[y]) {
        swap(x, y);
    }
    int logx, logy;
    for(logx=1; (1<<logx)<lvl[x]; ++logx);
    for(logy=1; (1<<logy)<lvl[y]; ++logy);
    int mn=INT_MAX;
    for(int i=logx; i>=0; --i) {
        if(lvl[x]-(1<<i)>=lvl[y]) {
            mn=min(mn, lift[i][x].second);
            x=lift[i][x].first;
        }
    }
    if(x==y)
        return mn;
    for(int i=logy; i>=0; --i) {
        if(lift[i][x].first!=0&&lift[i][x].first!=lift[i][y].first) {
            mn=min({mn, lift[i][x].second, lift[i][y].second});
            x=lift[i][x].first;
            y=lift[i][y].first;
        }
    }
    return min({mn, lift[0][x].second, lift[0][y].second});
}

int main()
{
    int n, m, p;
    si>>n>>m>>p;
    g.assign(n+5, {});
    for(int i=2; i<=n; ++i) {
        int u, v;
        si>>u>>v;
        g[u].push_back({i, v});
        g[i].push_back({u, v});
    }
    dfs(1, 0, INT_MAX);
    lift[0][0].second=INT_MAX;
    for(int i=1; i<LMax; ++i) {
        for(int j=0; j<=n; ++j) {
            pair<int, int> next=lift[i-1][lift[i-1][j].first];
            lift[i][j]={next.first, min(lift[i-1][j].second, next.second)};
        }
    }
    long long x, y, a, b, c, d;
    si>>x>>y>>a>>b>>c>>d;
    for(int i=1; i<=m; ++i) {
        long long z=lca(x, y);
        if(i>=m-p+1) {
            so<<z<<'\n';
        }
        int nx=(a*x+b*y)%n+1;
        int ny=(c*y+d*z)%n+1;
        //cout<<nx<<' '<<ny<<' '<<z<<'\n';
        x=nx;
        y=ny;
    }
    return 0;
}