Cod sursa(job #2329060)

Utilizator cipri321Marin Ciprian cipri321 Data 26 ianuarie 2019 12:24:11
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <vector>
#include <iostream>
#define DIM 32005
#define INF 2000000000
using namespace std;
ifstream fi("atac.in");
ofstream fo("atac.out");
int n,m,p;
vector<pair<int,int> > V[DIM];
int A[20][DIM],mn[20][DIM],l[DIM];
int x,y,z,a,b,c,d;
void dfs(int nod)
{
	l[nod]=l[A[0][nod]]+1;
	for(auto it:V[nod])
		if(!l[it.first])
		{
			A[0][it.first]=nod,mn[0][it.first]=it.second;
			dfs(it.first);
		}
}
pair<int,int> stramos(int q,int p)
{
	if(p==0)
		return {q,0};
	if(l[q]<=p)
		return {0,INF};
	int rez=q,rmn=INF;
	for(int i=30;i>=0;i--)
		if(p&(1<<i))
			rmn=min(rmn,mn[i][rez]),rez=A[i][rez];
	return {rez,rmn};
}
int query(int a,int b)
{
	if(a==b)
		return 0;
	if(l[a]<l[b])
		swap(a,b);
	pair<int,int> aux=stramos(a,l[a]-l[b]);
	a=aux.first;
	int rez=aux.second,st,dr;
	if(a==b)
		return rez;
	for(st=0,dr=n;st<dr;)
	{
		int mid=(st+dr)/2;
		//cout<<a<<" "<<b<<" ";
		pair<int,int> aux1=stramos(a,mid),aux2=stramos(b,mid);
		//cout<<mid<<" "<<aux1.first<<" "<<aux2.first<<"\n";
		if(aux1.first==aux2.first)
		{
			dr=mid;
			rez=min(aux1.second,aux2.second);
		}
		else
			st=mid+1;
	}
	return rez;
}
int main()
{
	fi>>n>>m>>p;
	for(int i=2;i<=n;i++)
	{
		int a,b;fi>>a>>b;
		V[i].push_back({a,b});
		V[a].push_back({i,b});
	}
	dfs(1);
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j<=n;j++)
		{
			A[i][j]=A[i-1][A[i-1][j]];
			mn[i][j]=min(mn[i-1][j],mn[i-1][A[i-1][j]]);
		}
		/*
	pair<int,int> p=stramos(7,1);
	cout<<p.first<<" "<<p.second<<"\n";
	*/
	fi>>x>>y>>a>>b>>c>>d;
	z=query(x,y);
	for(int i=2;i<=m;i++)
	{
		x=(1LL*x*a+1LL*y*b)%n+1;
		y=(1LL*y*c+1LL*z*d)%n+1;
		z=query(x,y);
		if(i>m-p)
			fo<<z<<"\n";
	}
	fi.close();
	fo.close();
	return 0;
}