Cod sursa(job #2644375)

Utilizator adiaioanaAdia R. adiaioana Data 24 august 2020 13:01:37
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda prbd2 Marime 2.48 kb
#include <fstream>
#include <cmath>
#include <map>
#include <vector>
#define INF 100010
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
vector <pair<int,int> > L[32010];
vector <pair<int,int> > eul;
vector <int> mn[20];
map <int, int> dest[32010];
map <int, int> :: iterator it,it1;
int N,M,P,pmin[33000],viz[32100],nn,dmin;
void dfs(int x, int nv);
void rmq();
void weirdfs(int x);
int answer(int x,int y);
int main()
{
    int xp,yp, Z,x,y,a,b,c,d,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<eul.size(); ++i)
        if(!pmin[eul[i].first])
            pmin[eul[i].first]=i;
    ///

    for(int i=1; i<=N; ++i)
        viz[i]=0;
    dest[1].insert({1,INF});
    weirdfs(1);

    ///

    for(int i=1, j=M; i<=M; j--, ++i)
    {
        Z=answer(x,y);
        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 p=1, i=0; p<eul.size(); ++i, p*=2)
        for(int ind=1; ind<eul.size()-p+1; ++ind)
            mn[i].push_back(0);
    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=min(pp.second,nod.second);
                dest[nod.first].insert({nn,dmin});
            }
            dest[nod.first].insert({x,nod.second});
            weirdfs(nod.first);
        }
}

int answer(int x,int y)
{
    if(x==y) return 0;
    int ax,ay,lca,lg,p2,Z;
    ax=pmin[x];
    ay=pmin[y];
    if(ax>ay) swap(ax,ay);
    lg=ay-ax+1;
    p2=log2(lg);
    lca=min(mn[p2][ax],mn[p2][ay-(1<<p2)+1]);
    ///

    it=dest[x].find(lca);
    it1=dest[y].find(lca);
    Z=min(it->second, it1->second);

    return Z;
}