fork download
copy 
  1. #include<stdio.h>
  2.  #include<stdlib.h>
  3. int visited[10005];
  4. int level[10005];
  5. int *a;
  6. int queue[10005];
  7.  int lim[10005];
  8. int front=0,rear=0;
  9.  
  10. int cmpfunc (const void * a, const void * b)
  11. {
  12.    return ( *(int*)a - *(int*)b );
  13. }
  14.  
  15. void playgame(int n)
  16. {
  17. int min=10005,flag=0,index,i,turn=0,max=0,j=1,k;;
  18.  
  19. min=1;
  20. max=n;;
  21. 	k=n;
  22. 	while(1)
  23. 	{
  24. 		flag=0;
  25. 		while(1)
  26. 		{
  27. 	//		printf("level is %d j is %d min is %d\n",level[j],j,min);
  28. 			if(level[j]==min&&j<=n)
  29. 			{
  30. 				flag=1;
  31. 		//		printf("Alice deleting %d\n",j);
  32. 				level[j++]=20000;
  33. 			}
  34. 			else break;
  35. 		}
  36. 			if(flag==0)break;
  37. 			turn++;
  38. 			min++;
  39.  
  40. 			flag=0;
  41. 			if(level[k]!=20000&&k>=0)
  42. 			{
  43. 				flag=1;
  44. 				level[k--]=20000;				
  45. 			}
  46. //		if(flag==0)printf("BOb didnt delete\n");	
  47. 		if(flag==0)break;
  48. 		turn++;
  49. 	//	printf("After bob turn is %d\n",turn);
  50. 		max--;
  51. 		flag=0;
  52.  
  53. 	}
  54.  
  55.  
  56. 	printf("%d\n",turn);
  57.  
  58. }
  59.  
  60. void insert(int x)
  61. {
  62.  
  63. 	  queue[rear++]=x;
  64. //	printf("%d inserted\n",queue[rear-1]);
  65.  
  66. }
  67.  
  68. int delete()
  69. {
  70. 	if(rear==front)
  71. 	{
  72. //		printf("Empty queue\n");
  73. 		return -1;	
  74. 	}
  75. 	else return queue[front++];
  76.  
  77. }
  78.  
  79.  
  80. void bfs(int n)
  81. {
  82. int start=1,temp,j=1;
  83. int lev=1,i;
  84. insert(start);
  85. visited[1]=1;
  86. level[1]=1;
  87. j=2;
  88. //	printf("Start insereted\n");
  89. 	while(front!=rear)
  90. 	{
  91. 		start=delete();
  92. 		if(start==1)lev++;
  93. 		else if(a[start*(n+2)+2]>=1&&a[start*(n+2)+2]<=10002)
  94. 		{
  95. 			lev=level[start]+1;
  96. 		//	printf("Start is %d lev incremented old lev was %d\n",start,level[start]);
  97. 		}
  98. 	//	lev=level[start]+1;
  99. 	//	printf("Start is %d lev is %d\n",start,lev);
  100. 		for(i=1;i<=n&&a[start*(n+2)+i]!=0&&a[start*(n+2)+i]<=10002;i++)
  101. 		{
  102. 			//printf("Checking element %d\n",a[start][i]);
  103. 			temp=a[start*(n+2)+i];
  104. //			printf("Temp=%d\n",temp);
  105. 			if(temp>=1)
  106. 			{
  107. 				if(visited[temp]!=1)
  108. 				{
  109. 					insert(temp);
  110. 					visited[temp]=1;
  111. 					level[temp]=lev;
  112. 	//				printf("Inserted is %d level is %d\n",temp,lev);
  113. 				}			
  114. 			}
  115. 		}
  116. 	}
  117.  
  118. }
  119.  
  120. int main()
  121. {
  122.  
  123. int i,j,test;
  124. int start,end,n,g;
  125.  
  126. scanf("%d\n",&test);
  127. //printf("test=%d\n",test);
  128.  
  129. while(test-->0)
  130. {
  131. 	scanf("%d",&n);
  132. 	front=rear=0;
  133. 	//printf("n=%d\n",n);
  134. 	if(n==1)
  135. 	{
  136. 		printf("1\n");
  137. 		continue;
  138. 	}
  139.  
  140. 	a=(int *)malloc((sizeof(int))*(n+2)*(n+2));
  141. //	printf("array allocated\n");
  142. 	memset(level,0,sizeof(level));
  143. //	memset(a,0,sizeof(a)*(n+2)*(n+2));
  144. 	memset(queue,0,sizeof(queue));
  145. 	memset(visited,0,sizeof(visited));
  146. 	memset(lim,0,sizeof(lim));
  147.  
  148. 	for(i=1;i<n;i++)
  149. 	{
  150. 		scanf("%d %d",&start,&end);
  151. 		a[start*(n+2)+lim[start]+1]=end;
  152. 		lim[start]=lim[start]+1;
  153.  
  154. 		a[end*(n+2)+lim[end]+1]=start;
  155. 		lim[end]=lim[end]+1;
  156.  
  157.  
  158. 		//	b[end][start]=1;
  159. 	}
  160. 	if(n==2)
  161. 	{
  162. 		printf("2\n");
  163. 		continue;
  164. 	}
  165.  
  166. /*	for(i=1;i<=n;i++)
  167. 	{	
  168. 		g=1;
  169. 		for(j=1;j<=n;j++)
  170. 		{
  171. 			if(b[i][j]==1)
  172. 			{
  173. 				a[i][g++]=j;
  174. 			}
  175. 		}
  176. 	}*//*
  177. 	for(i=1;i<=n;i++)
  178. 	{
  179. 		for(j=1;j<=n&&a[i*(n+2)+j]!=0;j++)
  180. 		{
  181. 			printf("i and j are %d %d element is %d\n",i,j,a[i*(n+2)+j]);
  182. 		}
  183. 		printf("\n");
  184. 	}*/
  185. 	//printf("levels assigned\n");
  186.  
  187. 	bfs(n);
  188. 	 qsort(level, n+1, sizeof(int), cmpfunc);
  189. 	playgame(n);
  190. 	//printf("levels are\n");
  191. 	for(i=1;i<=n;i++)
  192. 	{
  193. 		//printf("%d %d\n",i,level[i]);
  194. 	}
  195. 	free(a);
  196.  
  197. }
  198. return 0;
  199.  
  200. } 
  201.  
Success #stdin #stdout 0s 2584KB
comments (?)
stdin
copy 
8
1
2
2 1
2
1 2
1
6
1 2
1 3
1 4
1 5
4 6
11
1 10
1 3
10 4
10 5
3 6
3 7
4 8
5 9
9 2
9 11
12
1 2
1 3
2 4
2 5
3 6
5 7
6 10
7 8
7 9
10 11
11 12
11
1 10
1 6
10 7
6 9
7 8
9 4
8 3
8 5
4 2
2 11
stdout
copy 
1
2
2
1
3
7
8
6
https://ideone.com/TZdED1
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!