Cod sursa(job #2922859)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 10 septembrie 2022 13:16:47
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;


///rmq
class Rmq
{
    int n;
    vector<vector<int>>rmq;
    vector<int>lg;

    void build()
    {
        for(int j=1;(1<<j)<=n;j++)
        {
            for(int i=1;i+(1<<j)-1<=n;i++)
            {
                rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
            }
        }
    }
public:
    Rmq()
    {

    }
    Rmq(vector<int>&a)
    {
        n=(int)a.size()-1;
        lg.resize(n+1);
        lg[0]=lg[1]=0;
        for(int i=2;i<=n;i++)
        {
            lg[i]=lg[i/2]+1;
        }
        rmq=vector<vector<int>>(n+1,vector<int>(lg[n]+2));
        for(int i=1;i<=n;i++)
        {
            rmq[i][0]=a[i];
        }
        build();
    }
    int query(int l,int r)
    {
        int lung=lg[r-l+1];
        return min(rmq[l][lung],rmq[r-(1<<lung)+1][lung]);
    }
};

class heavy
{
    int n;
    vector<int>head,h,poz,t,dp;
    vector<int>e={0};
    Rmq rmq;
    void dfs1(vector<vector<int>>&g,int nod,int tata)
    {
        dp[nod]=1;
        t[nod]=tata;
        h[nod]=h[tata]+1;
        for(auto &c:g[nod])
        {
            if(c==tata)continue;
            dfs1(g,c,nod);
            dp[nod]+=dp[c];
        }
    }
    void dfs2(vector<vector<int>>&g,vector<int>&val,int nod,int tata,int lant)
    {
        if(lant==-1)
        {
            lant=nod;
        }
        head[nod]=lant;
        poz[nod]=(int)e.size();
        e.push_back(val[nod]);
        int maxx=0;
        dp[0]=0;
        for(auto &c:g[nod])
        {
            if(c==tata)continue;
            if(dp[c]>dp[maxx])
            {
                maxx=c;
            }
        }
        if(dp[nod]>1)
        {
            dfs2(g,val,maxx,nod,lant);
            for(auto &c:g[nod])
            {
                if(c==tata || c==maxx)continue;
                dfs2(g,val,c,nod,-1);
            }
        }
    }
public:
    void dfs(vector<vector<int>>&g,vector<int>&val)
    {
        dfs1(g,1,0);
        dfs2(g,val,1,0,-1);
    }
    heavy()
    {

    }
    heavy(vector<vector<int>>&g,vector<int>&val)
    {
        n=(int)g.size()-1;
        head.resize(n+1);
        h.resize(n+1);
        poz.resize(n+1);
        t.resize(n+1);
        dp.resize(n+1);
        h[0]=0;
        dfs(g,val);
        rmq=Rmq(e);
    }
    int query(int a,int b)
    {
        int rez=2e9;
        for(;head[a]!=head[b];b=t[head[b]])
        {
            if(h[head[a]]>h[head[b]])
            {
                swap(a,b);
            }
            rez=min(rez,rmq.query(poz[head[b]],poz[b]));
        }
        if(h[a]>h[b])
        {
            swap(a,b);
        }
        if(a!=b)
        {
            rez=min(rez,rmq.query(poz[a]+1,poz[b]));
        }
        return rez;
    }
};
main()
{
    ifstream cin("atac.in");
    ofstream cout("atac.out");
    int n,m,p;
    cin>>n>>m>>p;
    vector<int>val(n+1,0);
    vector<vector<int>>a(n+1);
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x>>val[i];
        a[x].push_back(i);
        a[i].push_back(x);
    }
    heavy tree(a,val);
    int x,y,a2,b,c,d;
    cin>>x>>y>>a2>>b>>c>>d;
    for(int i=1;i<=m;i++)
    {
        int z=tree.query(x,y);
        if(x==y)
        {
            z=0;
        }
        if(m-p+1<=i)cout<<z<<'\n';
        x=(a2*x+b*y)%n+1;
        y=(c*y+d*z)%n+1;
    }
}