Cod sursa(job #2644362)

Utilizator adiaioanaAdia R. adiaioana Data 24 august 2020 12:43:11
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda prbd2 Marime 2.5 kb
#include <fstream>
#include <cmath>
#include <map>
#include <vector>
#define INF 3200000000
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
vector <pair<int,int> > L[33000];
vector <pair<int,int> > eul;
map <int, long long> dest[33000];
map <int, long long> :: iterator it,it1;
int N,M,P,pmin[33000],mn[20][65000],viz[33000],nn;
long long dmin;
void dfs(int x, int nv);
void rmq();
void weirdfs(int x);
int main()
{
    int xp,yp, Z,x,y,a,b,c,d,lca,ax,ay,u,v,lg,p2;
    cin>>N>>M>>P;
    for(int i=2; i<=N; ++i)
    {
        cin>>u>>v;
        L[i].push_back({u,v});
        L[u].push_back({i,v});
    }
    ///
    cin>>x>>y>>a>>b>>c>>d;
    eul.push_back({0,0});
    dfs(1,0);
    rmq();

    for(int i=1; i<=N; ++i)
        viz[i]=0;
    dest[1].insert({1,INF});
    weirdfs(1);
    /*for(int i=1; i<=N; ++i)
    {
        cout<<i<<' ';
        for(auto pp: dest[i])
            cout<<pp.first<<' '<<pp.second<<' ';
        cout<<'\n';
    }*/

    for(int i=1; i<eul.size(); ++i)
        if(!pmin[eul[i].first])
            pmin[eul[i].first]=i;

    for(int i=1, j=M; i<=M; j--, ++i)
    {
        ax=pmin[x];
        ay=pmin[y];
        lg=abs(ay-ax+1);
        if(ax>ay) swap(ax,ay);
        p2=log2(lg);
        lca=min(mn[p2][ax],mn[p2][ax+(1<<p2)-1]);
        if(x==y) Z=0;
        else{
            it=dest[x].find(lca);
            it1=dest[y].find(lca);
            Z=min(it->second, it1->second);
        }
        if(j<=P) cout<<Z<<'\n';
        xp=(x*a+y*b)%N+1;
        yp=(y*c+Z*d)%N+1;
        x=xp; y=yp;
    }
    return 0;
}

void dfs(int x, int nv)
{
    eul.push_back({x,nv});
    viz[x]=1;
    for(auto nod : L[x])
        if(!viz[nod.first])
        {
            dfs(nod.first,nv+1);
            eul.push_back({x,nv});
        }
}

void rmq()
{
    for(int i=1; i<eul.size(); ++i)
        mn[0][i]=eul[i].first;
    for(int p=2, i=1; p<eul.size(); ++i, p*=2)
        for(int ind=1; ind<eul.size()-p+1; ++ind)
            mn[i][ind]=min(mn[i-1][ind], mn[i-1][ind+p/2]);;
}

void weirdfs(int x)
{
    viz[x]=1;
    for(auto nod : L[x])
        if(!viz[nod.first])
        {
            for(auto pp: dest[x])
            {
                nn=pp.first;
                dmin=pp.second;
                if(dmin>nod.second) dmin=nod.second;
                dest[nod.first].insert({nn,dmin});
            }
            dest[nod.first].insert({x,nod.second});
            weirdfs(nod.first);
        }
}