Cod sursa(job #2632205)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 2 iulie 2020 15:38:38
Problema Atac Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>
#define DIM 35000
#define DIMM 500010
#define INF 2000000000
using namespace std;

int E[DIM*4],p[DIM*4],first[DIM],val[DIM],ans[DIMM],level[DIM];
int nr_chains,n,m,P,i,j,x,y,sol,k,cost,a,b,c,d;
int stramos[22][DIM],dp[22][DIM];
pair <int,int> rmq[22][DIM*4];
vector <pair<int,int> > L[DIM];


void dfs (int nod, int tata){

    level[nod] = 1 + level[tata];
    E[++k] = nod;
    first[nod] = k;

    for (auto it : L[nod]){
        int vecin = it.first, cost = it.second;
        if (vecin != tata){
            stramos[0][vecin] = nod;
            dp[0][vecin] = cost;

            dfs (vecin,nod);
            E[++k] = nod;
        }}}

int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy - posx + 1];
    pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
    return E[sol.second];
}


void query (int x, int y){
    if (x == y)
        return;

    int lca = get_lca (x,y);

    for (int i=17;i>=0;i--){
        int nod = stramos[i][x];
        if (level[nod] >= level[lca]){
            sol = min (sol,dp[i][x]);
            x = nod;
        }}

    for (int i=17;i>=0;i--){
        int nod = stramos[i][y];
        if (level[nod] >= level[lca]){
            sol = min (sol,dp[i][y]);
            y = nod;
        }}}

int main (){

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

    fin>>n>>m>>P;
    for (i=2;i<=n;++i){
        fin>>x>>cost;
        L[i].push_back(make_pair(x,cost));
        L[x].push_back(make_pair(i,cost));
    }

    dfs (1,0);


    for (i=1;i<=k;++i){
        rmq[0][i] = make_pair(level[E[i]],i);
        if (i > 1)
            p[i] = p[i/2] + 1;
    }

    for (i=1;(1<<i)<=k;++i)
        for (j=1;j<=k;++j){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

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


    fin>>x>>y>>a>>b>>c>>d;
    sol = INF;
    query (x,y);
    if (x == y)
        sol = 0;

    if (m == P)
        fout<<sol<<"\n";

    for (i=2;i<=m;++i){
        x = (1LL * x * a + 1LL * y * b) % n + 1;
        y = (1LL * y * c + 1LL * sol * d) % n + 1;
        sol = INF;
        query (x,y);
        if (x == y)
            sol = 0;

        if (i >= m-P+1)
            fout<<sol<<"\n";
    }

    return 0;
}