Cod sursa(job #3150125)

Utilizator CelestinNegraru Celestin Celestin Data 14 septembrie 2023 21:39:34
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 32002
#define logmax 17
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
vector<pair<int,int>> V[nmax];
vector<int> solutie;
int n,m,p,x,y,z,a,b,c,d,k,euler[2*nmax],fap[nmax],lvl[nmax],rmq[logmax][nmax],lg[2*nmax],nivele[nmax];
pair<int,int> dp[logmax][nmax];
bool viz[nmax];
void dfs(int x,int lv)
{
    viz[x]=true;
    nivele[x]=lv;
    euler[++k]=x;
    lvl[k]=lv;
    fap[x]=k;
    for(auto a:V[x])
    {
        if(!viz[a.first])
        {
            dp[0][a.first].first=x;
            dp[0][a.first].second=a.second;
            dfs(a.first,lv+1);
            euler[++k]=x;
            lvl[k]=lv;
        }
    }
}
void compute_rmq()
{
    lg[1]=0;
    for(int i=2;i<=k;i++)
        lg[i]=lg[i>>1]+1;
    for(int i=1;i<=k;i++)
        rmq[0][i]=i;
    for(int i=1;i<=lg[k];i++)
    {
        for(int j=1;j+(1<<i)-1<=k;j++)
        {
            rmq[i][j]=lvl[rmq[i-1][j]]<lvl[rmq[i-1][j+(1<<(i-1))]]?rmq[i-1][j]:rmq[i-1][j+(1<<(i-1))];
        }
    }
}
int lca(int x,int y)
{
    int st=fap[x],dr=fap[y];
    if(st>dr)
        swap(st,dr);
    int lin=lg[dr-st+1];
    int ans=lvl[rmq[lin][st]]<lvl[rmq[lin][dr-(1<<lin)+1]]?rmq[lin][st]:rmq[lin][dr-(1<<lin)+1];
    return euler[ans];
}
void compute_dp()
{
    for(int i=1;i<=lg[n];i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j].first=dp[i-1][dp[i-1][j].first].first;
            dp[i][j].second=min(dp[i-1][j].second,dp[i-1][dp[i-1][j].first].second);
        }
    }
}
int ans(int x,int y)
{
    int niv=nivele[x]-nivele[y],curr=x;
    int ans=0x3f3f3f3f;
    for(int i=0;(1<<i)<=niv;i++)
    {
        if(niv&(1<<i))
        {
            ans=min(ans,dp[i][curr].second);
            curr=dp[i][curr].first;
        }
    }
    return ans;
}
int main() {
    f >> n >> m >> p;
    for (int i = 2; i <= n; i++) {
        int u, v;
        f >> u >> v;
        V[u].push_back(make_pair(i, v));
        V[i].push_back(make_pair(u, v));
    }
    dfs(1, 0);
    compute_rmq();
    compute_dp();
    f>>x>>y>>a>>b>>c>>d;
    int z;
    int lc=lca(x,y);
    z=min(ans(x,lc),ans(y,lc));
    solutie.push_back(z);
    for(int i=2;i<=m;i++)
    {
        int x1=(x*a+y*b)%n+1;
        int y1=(y*c+z*d)%n+1;
        int lc=lca(x1,y1);
        z=min(ans(x1,lc),ans(y1,lc));
        solutie.push_back(z);
        x=x1;
        y=y1;
    }
    for(int i=p-1;i<solutie.size();i++)
        g<<solutie[i]<<'\n';
    return 0;
}