Cod sursa(job #3288054)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 20 martie 2025 13:47:47
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <vector>
#define nmax 32001
#define inf 1e9
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
int n,m,p,x,y,z,a,b,c,d,k,niv[nmax],rmq[16][nmax],mini[16][nmax];
vector<pair<int,int>>v[nmax];
void dfs(int nod,int t){
    niv[nod]=niv[t]+1;
    rmq[0][nod]=t;
    for(auto i:v[nod])
        if(i.first!=t){
            mini[0][i.first]=i.second;
            dfs(i.first,nod);
        }
}
int lca(int x,int y){
    int r=inf;
    if(niv[x]<niv[y])
        swap(x,y);
    for(int i=15;i>=0;i--)
        if(niv[rmq[i][x]]>=niv[y]){
            r=min(r,mini[i][x]);
            x=rmq[i][x];
        }
    if(x==y)
        return r;
    for(int i=15;i>=0;i--)
        if(rmq[i][x]!=0&&rmq[i][y]!=0&&rmq[i][x]!=rmq[i][y]){
            r=min(r,min(mini[i][x],mini[i][y]));
            x=rmq[i][x];
            y=rmq[i][y];
        }
    return min(r,min(mini[0][x],mini[0][y]));
}
signed main()
{
    cin>>n>>m>>p;
    for(int i=2;i<=n;i++){
        cin>>x>>y;
        v[x].push_back({i,y});
        v[i].push_back({x,y});
    }
    for(int i=0;(1<<i)<=n;i++)
        for(int j=0;j<=n;j++)
            mini[i][j]=inf;
    dfs(1,0);
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n;j++){
            rmq[i][j]=rmq[i-1][rmq[i-1][j]];
            mini[i][j]=min(mini[i-1][j],mini[i-1][rmq[i-1][j]]);
        }
    cin>>x>>y>>a>>b>>c>>d;
    for(int i=1;i<=m;i++){
        if(x==y)
            z=0;
        else
            z=lca(x,y);
        if(i>m-p)
            cout<<z<<'\n';
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    return 0;
}