Cod sursa(job #2633883)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 9 iulie 2020 00:44:52
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream in ("atac.in");
ofstream out("atac.out");
const int oo=2e9;
int n, m, p, X, Y, A, B, C, D, x, cost;
vector <short> level;
vector <vector <pair <short, int> > > muchii;
vector <vector <short> >  sparse;
vector <vector <int> > dp;
void dfs(int nod, int ant, int lev, int cost)
{
    sparse[nod].push_back(ant);
    dp[nod].push_back(cost);

    level[nod]=lev;

    for(int put=1; lev-(1<<put)>=1; put++)
    {
        int ancestor=sparse[nod][put-1];
        sparse[nod].push_back(sparse[ancestor][put-1]);
        dp[nod].push_back(min(dp[nod][put-1], dp[ancestor][put-1]));
    }
    for(auto & x:muchii[nod])
        if(!level[x.first])
            dfs(x.first, nod, lev+1, x.second);
}
inline int find_sol(int i, int j)
{
    if(i==j) return 0;

    if(level[i]<level[j]) swap(i, j);

    int levi=level[i], levj=level[j], mini=oo;

    int put=log2(levi-levj);

    while(levi>levj)
        if(levi-(1<<put)>=levj)
            mini=min(mini, dp[i][put]), levi-=(1<<put), i=sparse[i][put];
    put=log2(levi-1);

    for( ;put>0; put--)
        if(sparse[i][put]!=sparse[j][put])
           mini=min({mini, dp[i][put], dp[j][put]}), levi-=(1<<put), i=sparse[i][put], j=sparse[j][put];

    while(i!=j)
    {
        mini=min({mini, dp[i][0], dp[j][0]});
        i=sparse[i][0]; j=sparse[j][0];
    }

    return mini;
}

int main()
{
    in>>n>>m>>p;
    muchii.resize(n+1); level.resize(n+1);
    sparse.resize(n+1); dp.resize(n+1);
    for(int i=2; i<=n; i++)
    {
        in>>x>>cost;
        muchii[i].push_back({x, cost});
        muchii[x].push_back({i, cost});
    }

    dfs(1, 0, 1, 0);
    muchii.clear(); muchii.shrink_to_fit();

    in>>X>>Y>>A>>B>>C>>D;
    for(int q=1; q<=m; q++)
    {
        int nrB=find_sol(X, Y);
        if(q>=m-p+1)
            out<<nrB<<"\n";
        X=(X*A+Y*B) % n + 1;
        Y=(Y*C+nrB*D) % n + 1;
    }
    return 0;
}