Pagini recente » Cod sursa (job #1883283) | Cod sursa (job #2895803) | Cod sursa (job #2974654) | Cod sursa (job #2723798) | Cod sursa (job #3244532)
#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];
}
}
if(x!=y)
{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;
}