Cod sursa(job #393229)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 9 februarie 2010 09:02:00
Problema Stramosi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <vector>

#define Nmax 250005
#define Mmax 300005

using namespace std;

vector <int> A[Nmax], B[Nmax], C[Nmax];

int n, m, p, q, x, niv, nod;
int S[Nmax], SOL[Mmax];
int i, j;


FILE * f = fopen ("stramosi.in", "r");
FILE * g = fopen ("stramosi.out", "w");


void DFS (int niv, int nod){
	//viz [nod] = 1;
	S [niv] = nod;
	for (i = 0 ; i < (int)A[nod].size() ; i++){
		//if (viz[ A[nod][i] ] != 1){
			DFS (niv + 1, A[nod][i]);
			for (j = 0 ; j < (int)B[nod].size() ; j++)
				if (B[nod][j] < niv)
					SOL [ C[nod][j] ] = S[niv - B[nod][j]];
			
		}
}


int main (){
	
	fscanf (f, "%d %d", &n, &m);
	
	for (i = 1 ; i <= n ; i++){
		fscanf (f, "%d", &x);
		A[x].push_back(i);
	}
	
	for (i = 1 ; i <= m ; i++){
		fscanf (f, "%d %d", &q, &p);
		B[q].push_back(p);		
		B[q].push_back(i);
	}
	
	DFS(1, 0);
	
	for (i = 1 ; i <= m ; i++)
		fprintf (f, "%d\n", SOL [i]);
		
	
	fclose(f);
	fclose(g);
	return 0;
}