Cod sursa(job #3944)

Utilizator rapidu36Victor Manz rapidu36 Data 29 decembrie 2006 18:04:30
Problema Stramosi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<stdio.h>
#include<stdlib.h>
#define N 250001
#define M 300001
struct quest{
	int p,q,r,ord;
};
quest intreb[M],cintreb[M];
int nrs[N],n,m,nr,*(a[N]),nrv[N],tata[N],v[N],prim_int[N],ultim_int[N];
int compar_v(const void * a, const void * b)
{
	quest *x=(quest*)a,*y=(quest*)b;
	return x->q-y->q;
}
int compar_o(const void * a, const void * b)
{
	quest *x=(quest*)a,*y=(quest*)b;
	return x->ord-y->ord;
}
void citire(){
	int i,x;
	FILE *in=fopen("stramosi.in","r");
	fscanf(in,"%d%d",&n,&m);
	for(i=1;i<=n;i++){
		fscanf(in,"%d",&x);
		tata[i]=x;
		nrv[x]++;
	}
	for(i=1;i<=n;i++){
		a[i]=new int[nrv[i]+1];
		a[i][0]=0;
	}
	for(i=1;i<=n;i++){
		x=tata[i];
		if(x)
			a[x][++a[x][0]]=i;
	}
	for(i=0;i<m;i++){
		fscanf(in,"%d%d",&intreb[i].q,&intreb[i].p);
		intreb[i].ord=i;
		cintreb[i]=intreb[i];
	}
	//qsort (values, 6, sizeof(int), compare);
	qsort(intreb,m,sizeof(intreb[0]),compar_v);
	for(i=1;i<=n;i++){
		prim_int[i]=-1;
		ultim_int[i]=m-1;
	}
	prim_int[intreb[0].q]=0;
	for(i=1;i<m;i++)
		if(intreb[i].q!=intreb[i-1].q){
			ultim_int[intreb[i-1].q]=i-1;
			prim_int[intreb[i].q]=i;
		}
	fclose(in);
}
/*
void proba(){
	FILE *f=fopen("proba.txt","w");
	int i,j;
	quest*jj;
	fprintf(f,"Listele:\n");
	for(i=1;i<=n;i++){
		fprintf(f,"cei %d fii ai lui %d: ",a[i][0],i);
		for(j=1;j<=a[i][0];j++)
			fprintf(f,"%d ",a[i][j]);
		fprintf(f,"\n");
	}
	fprintf(f,"Intrebarile:\n");
	for(i=0;i<m;i++)
		fprintf(f,"care este stramosul nr %d al lui %d?\n",intreb[i].p,intreb[i].q);
	fprintf(f,"Stramosii:\n");

	fprintf(f,"Intrebarile grupate pe noduri:\n");
	for(i=1;i<=n;i++){
		fprintf(f,"intrebarile lui %d: ",i);
		if(prim_int[i]>=0)
			for(j=prim_int[i];j<=ultim_int[i];j++)
				fprintf(f,"(%d,%d,%d) ",intreb[j].q,intreb[j].p,intreb[j].ord);
		fprintf(f,"\n");
	}
	fclose(f);
}

int log2(int x){
	int p=1,r=0;
	if(!x)
		return 0;
	while(p<=x){
		p*=2;
		r++;
	}
	return r;
}
*/
void df(int x){
	//int i=0,p,p2=1;
	int i,y,*iii;
	v[++nr]=x;
	quest *ii;
	/*
	p=log2(nr-1);
	nrs[x]=p;
	stra[x]=new int[p];
	stra[x][i]=x;
	while(nr>p2){
		stra[x][++i]=v[nr-p2];
		p2=p2+2*p2;
	}
	*/
	if(prim_int[x]>=0)
		for(i=prim_int[x];i<=ultim_int[x];i++){
			y=v[nr-intreb[i].p];
			intreb[i].r=y;
			cintreb[intreb[i].ord].r=y;
		}
	/*
	if(prim_int[x])
		for(ii=prim_int[x];ii!=ultim_int[x];ii++){
			y=v[nr-ii->p];
			ii->r=y;
			cintreb[ii->ord].r=y;
		}
	*/
	for(i=1;i<=a[x][0];i++)
		df(a[x][i]);
	/*
	for(iii=a[x]+1;iii!=a[x]+a[x][0]+1;iii++)
		df(*iii);
	*/
	nr--;
}

void parc(){
	int i;
	for(i=1;i<=n;i++)
		if(!tata[i]){
			nr=0;
			df(i);
		}
}
void scrie(){
	int i;
	FILE *out=fopen("stramosi.out","w");
	//qsort(intreb,m,sizeof(intreb[0]),compar_o);
	for(i=0;i<m;i++)
		fprintf(out,"%d\n",cintreb[i].r);
	fclose(out);
}
int main(){
	citire();
	//proba();
	parc();
	scrie();
	return 0;
}