Cod sursa(job #2633896)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 9 iulie 2020 01:21:03
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("atac.in");
ofstream out("atac.out");
const int oo=2e9, nmax=32003;
int n, m, p, X, Y, A, B, C, D, x, cost;
short loga[nmax], level[nmax];
vector <pair <short, int> > muchii[nmax];
short sparse[nmax][17];
int dp[nmax][17];
void dfs(int nod)
{
    for(int put=1; level[nod]-(1<<put)>=1; put++)
    {
        int ancestor=sparse[nod][put-1];
        sparse[nod][put]=sparse[ancestor][put-1];
        dp[nod][put]=min(dp[nod][put-1], dp[ancestor][put-1]);
    }
    for(auto & x:muchii[nod])
        if(!level[x.first])
        {
            sparse[x.first][0]=nod;
            dp[x.first][0]=x.second;
            level[x.first]=level[nod]+1;
            dfs(x.first);
        }
}
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=loga[levi-levj];

    while(levi>levj)
    {
        if(levi-(1<<put)>=levj)
            mini=min(mini, dp[i][put]), levi-=(1<<put), i=sparse[i][put];
        put--;
    }
    put=loga[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()
{
    loga[1]=0;
    in>>n>>m>>p;
    for(int i=2; i<=n; i++)
        loga[i]=loga[i/2]+1;

    for(int i=2; i<=n; i++)
    {
        in>>x>>cost;
        muchii[i].push_back({x, cost});
        muchii[x].push_back({i, cost});
    }
    level[1]=1; dfs(1);
    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=((long long)X*A+(long long)Y*B) % n + 1;
        Y=((long long)Y*C+(long long)nrB*D) % n + 1;
    }
    return 0;
}