Cod sursa(job #496391)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 28 octombrie 2010 19:54:37
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Nmax 30000+2
#define pb push_back
#define INF 2147000000

using namespace std;

char *s[2];
vector< int > v[Nmax];
int Win[Nmax],use[Nmax],TT[Nmax],ind[Nmax],Niv[Nmax],marc[Nmax],X[Nmax],Next[Nmax];
int T,N,M,K,win;

inline int cmp(int i,int j){
	return Niv[i] > Niv[j];
}

void df(int x){
	vector< int >:: iterator it;
	use[x]=1; Niv[x]=Niv[TT[x]]+1;
	for(it=v[x].begin(); it!=v[x].end(); ++it)
		if( ! use[*it] || Niv[x]+1>Niv[*it] )
			TT[*it]=x, df(*it);
}	

void work(){
	int i;
	vector< int >:: iterator it;
	
	for(i=1;i<=N;++i) 
		if(!marc[i])// in i nu intra niciun nod
			df(i);

	for(i=1;i<=N;++i) ind[i]=i;
	sort(ind+1,ind+N+1,cmp); // sortez dupa nivel >
	
	for(i=1;i<=N;++i)
		for(it=v[ind[i]].begin(); it!=v[ind[i]].end(); ++it)
			if( !Win[*it] )
				Win[ind[i]] = 1, Next[ind[i]]=*it;

}

int main(){
	int i,q,x,y,wh;
	freopen("pioni.in","r",stdin);
	freopen("pioni.out","w",stdout);
	scanf("%d%d%d",&T,&N,&M);
	for(i=1;i<=M;++i){
		scanf("%d%d",&x,&y);
		marc[y]=1;
		v[x].pb(y);
	}
	
	s[1]="Nargy"; s[0]="Fumeanu";
	work();
	
	for(q=1; q<=T; ++q){
		scanf("%d",&K);
		win=0; wh=0;
		for(i=1;i<=K;++i){
			scanf("%d",&X[i]);
			if( Win[X[i]] ){++win;}
		}
		printf("%s\n",s[win>0]);
		if(win){
			printf("%d ",win);
			for(i=1;i<=K;++i) 
				if( Win[X[i]] )printf("%d %d ",X[i],Next[X[i]]);
			printf("\n");
		}
	}
	
	fclose(stdin); fclose(stdout);
	return 0;
}