Cod sursa(job #494838)

Utilizator space.foldingAdrian Soucup space.folding Data 23 octombrie 2010 02:43:57
Problema Stramosi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <vector>
#include <map>
int v[250001], leaves[250001];
int M[20][250000];
int main ()
{
	std::vector < std::vector <int> > vv;
	
	
	FILE *in=fopen("stramosi.in", "r"), *out=fopen("stramosi.out", "w");
	int n, m, value, s1, s2;
	fscanf(in, "%d%d", &n, &m);
	for(int i=0; i<n; ++i)
	{
		fscanf(in, "%d", v+i+1);
		leaves[v[i+1]]=-1;
	}
	vv.push_back(std::vector <int>());//primul nu ne intereseaza vv[0]
		
	for(int i=1; i<=n; ++i)
	{
		if(!leaves[i])
		{
			value=i;
			vv.push_back(std::vector <int>());
			

			vv[vv.size()-1].push_back(i);
			leaves[value]=vv.size()-1;
			
			int j=0;
			while(v[value]!=0)
			{
				j++;
				value=v[value];
				vv[vv.size()-1].push_back(value); //pentru fiecare pereche <value, frunza> doresc sa cunosc lungimea lantului
				leaves[value]=vv.size()-1;
				M[vv.size()-1][value]=j;
			}
		}
	}				
			

	for(int i=0; i<m; ++i)
	{
		fscanf(in, "%d%d", &s1, &s2);
		value=leaves[s1];
		

		if(M[value][s1]+s2<vv[value].size())
			fprintf(out, "%d\n", vv[value][M[value][s1]+s2]);
		else
			fprintf(out, "0\n");
	}
	return 0;
}