Cod sursa(job #1992550)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 20 iunie 2017 18:23:29
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <map>
#include <string>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm> 
#include <ctime>

#define MaxN 32005
#define INF 2140000000
 
using namespace std;

FILE *IN,*OUT;

struct G
{
	int father,minc;
}Graph[15][MaxN];
int N,M,P,X,Y,A,B,C,D,depth[MaxN],l[MaxN],Log[MaxN];
bool found[MaxN];
void DFS(int node)
{
	if(Graph[0][node].father==0)
		depth[node]=1,found[node]=true;
	else
	{
		if(!found[Graph[0][node].father])
			DFS(Graph[0][node].father);
		depth[node]=1+depth[Graph[0][node].father];
		found[node]=true;
	}
}
void Precalc(int node)
{
	for(int i=1;i<15;i++)
	{
		Graph[i][node].father=Graph[i-1][Graph[i-1][node].father].father;
		Graph[i][node].minc=min(Graph[i-1][node].minc,Graph[i-1][Graph[i-1][node].father].minc);
	}
}
bool cond(int a,int b)
{
	return depth[a]<depth[b];
}
int LCA(int a,int b)
{
	int Min=INF;
	if(a==b)
		return 0;
	if(depth[a]>depth[b])
	{
		for(int i=Log[depth[a]];i>=0;i--)
			if(depth[a]-(1<<i)>=depth[b])
				Min=min(Min,Graph[i][a].minc),a=Graph[i][a].father;
	}
	if(depth[a]<depth[b])
	{
		for(int i=Log[depth[b]];i>=0;i--)
			if(depth[b]-(1<<i)>=depth[a])
				Min=min(Min,Graph[i][b].minc),b=Graph[i][b].father;
	}
	if(a!=b)
	{
		for(int i=Log[depth[a]];i>=0;i--)
			if(Graph[i][a].father!=Graph[i][b].father)
				Min=min(Min,min(Graph[i][a].minc,Graph[i][b].minc)),a=Graph[i][a].father,b=Graph[i][b].father;
		Min=min(Min,min(Graph[0][a].minc,Graph[0][b].minc));
	}
	return Min;
}
int main()
{
	IN=fopen("atac.in","r");
	OUT=fopen("atac.out","w");

	fscanf(IN,"%d%d%d",&N,&M,&P);
	for(int i=2;i<=N;i++)
		Log[i]=1+Log[i/2];
	for(int i=2;i<=N;i++)
		fscanf(IN,"%d%d",&Graph[0][i].father,&Graph[0][i].minc);
	fscanf(IN,"%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
	for(int i=1;i<=N;i++)
		if(!found[i])
			DFS(i),l[i]=i;
	sort(l+1,l+1+N,cond);
	for(int i=1;i<=N;i++)
		Precalc(l[i]);
	for(int i=1;i<=M;i++)
	{
		int Z=LCA(X,Y);
		int Xp=(X*A+Y*B)%N+1;
		int Yp=(Y*C+Z*D)%N+1;
		if(M-i<P)
			fprintf(OUT,"%d\n",Z);
		X=Xp,Y=Yp;
	}
	return 0;
}