Cod sursa(job #3244530)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 25 septembrie 2024 10:20:21
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <vector>
#include <map>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int N=32001,bit=15,M=5e5+1;
int raspuns[M];
vector<int>adj[N];
long long n,m,p;
map<pair<int,int>,int> mp;
int lift[N][bit],adancime[N];
int cost_lift[N][bit];
void precalc(int nod,int p)
{
    adancime[nod]=adancime[p]+1;
    lift[nod][0]=p;
    cost_lift[nod][0]=mp[ {nod,p}];

    for(int i=1; i<bit; i++)
    {
        lift[nod][i]=lift[lift[nod][i-1]][i-1];
        cost_lift[nod][i]=min(cost_lift[nod][i-1],cost_lift[lift[nod][i-1]][i-1]);
    }
    for(auto u:adj[nod])
    {
        if(u!=p)
            precalc(u,nod);
    }
}
int oras1,oras2,a,b,c,d;//;
void citeste()
{
    cin>>n>>m>>p;
    for(int i=2; i<=n; i++)
    {
        int ind,cost;
        cin>>ind>>cost;
        adj[i].push_back(ind);
        adj[ind].push_back(i);
        mp[ {i,ind}]=cost;
        mp[ {ind,i}]=cost;
    }
    cin>>oras1>>oras2>>a>>b>>c>>d;
}
void rezolva(int x,int y,int i)
{
    if(x==y)
    {
        raspuns[i]=0;
        return;
    }
    if(adancime[x]<adancime[y])
        swap(x,y);
    int ans=1e9;
    int dist=(adancime[x]-adancime[y]);
    for(int i=14;i>=0;i--)
    {
        int salt=(1<<i);
        if(salt>dist)
            continue;
        ans=min(ans,cost_lift[x][i]);
        x=lift[x][i];
        dist-=salt;
    }
    for(int i=14;i>=0;i--)
    {
        if(lift[x][i]!=lift[y][i])
        {
            ans=min(ans,cost_lift[x][i]);
            ans=min(ans,cost_lift[y][i]);
            x=lift[x][i];
            y=lift[y][i];
        }
    }
    ans=min(ans,cost_lift[x][0]);
    ans=min(ans,cost_lift[y][0]);
    raspuns[i]=ans;
}
int main()
{
    citeste();
    precalc(1,0);
    for(int i=1;i<=m;i++)
    {
        int pred1=oras1,pred2=oras2;
        rezolva(oras1,oras2,i);
        oras1=(pred1*a+pred2*b)%n+1;
        oras2=(pred2*c+raspuns[i]*d)%n+1;
    }
    for(int i=(m-p+1);i<=m;i++)
        cout<<raspuns[i]<<'\n';
    return 0;
}