Source code for submission s974

Go to diff to previous submission

fn.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <set>
  5.  
  6. using namespace std;
  7. typedef set<int> SET;
  8. typedef SET::iterator IT;
  9.  
  10. typedef struct EDGE
  11. {
  12. 	int u;
  13. 	int v;
  14. }
  15. EDGE;
  16.  
  17. EDGE Input[100000];
  18.  
  19. int Degree[100000];
  20. int Fol[100000];
  21. int iFol[100000];
  22. int CurIndex[100000];
  23.  
  24. int Visited[100000];
  25. int List[100000]; //D3
  26. int nList;
  27.  
  28. int Q[100000];
  29. int QBeg, QEnd;
  30.  
  31. int main()
  32. {
  33. 	int n, m, mm;
  34. 	while(scanf("%d%d", &n, &m) > 0)
  35. 	{
  36. 		memset(Degree, 0, sizeof(Degree));
  37. 		memset(CurIndex, 0, sizeof(CurIndex));
  38. 		memset(Visited, 0, sizeof(Visited));
  39.  
  40. 		for(int i = 0; i < m; i++)
  41. 		{
  42. 			scanf("%d%d", &(Input[i].u), &(Input[i].v));
  43. 			Input[i].u--;
  44. 			Input[i].v--;
  45.  
  46. 			Input[i + m].u = Input[i].v;
  47. 			Input[i + m].v = Input[i].u;
  48.  
  49. 			Degree[Input[i].u]++;
  50. 			Degree[Input[i].v]++;
  51. 		}
  52.  
  53. 		iFol[0] = 0;
  54. 		for(int i = 0; i < n; i++)
  55. 		{
  56. 			iFol[i + 1] = iFol[i] + Degree[i];
  57.  
  58. 			if(Degree[i] >= 4)
  59. 			{
  60. 				printf("YES\n");
  61. 				goto NEXT_INSTANCE;
  62. 			}
  63. 		}
  64.  
  65. 		mm = m * 2;
  66. 		for(int i = 0; i < mm; i++)
  67. 		{
  68. 			int e = Input[i].u;
  69. 			Fol[iFol[e] + CurIndex[e]++] = Input[i].v;
  70. 		}
  71.  
  72. 		for(int i = 0; i < n; i++)
  73. 		//components
  74. 		{
  75. 			if(Visited[i])
  76. 			{
  77. 				continue;
  78. 			}
  79.  
  80. 			nList = 0;
  81. 			QBeg = 0;
  82. 			QEnd = 0;
  83. 			Q[QEnd++] = i;
  84. 			Visited[i] = 1;
  85.  
  86. 			while(QBeg < QEnd)
  87. 			{
  88. 				int cur = Q[QBeg++];
  89. 				for(int j = iFol[cur]; j < iFol[cur + 1]; j++)
  90. 				{
  91. 					int t = Fol[j];
  92.  
  93. 					if(!(Visited[t]))
  94. 					{
  95. 						Visited[t] = 1;
  96. 						Q[QEnd++] = t;
  97. 					}
  98. 				}
  99. 			}
  100.  
  101. 			for(int j = 0; j < QEnd; j++)
  102. 			{
  103. 				if(Degree[Q[j]] == 3)
  104. 				{
  105. 					List[nList++] = Q[j];
  106. 				}
  107. 			}
  108.  
  109. 			for(int j = 0; j < nList; j++)
  110. 			{
  111. 				for(int k = j + 1; k < nList; k++)
  112. 				{
  113. 					int u = List[j];
  114. 					int v = List[k];
  115.  
  116. 					SET set;
  117. 					set.clear();
  118. 					set.insert(Fol[iFol[u] + 0]);
  119. 					set.insert(Fol[iFol[u] + 1]);
  120. 					set.insert(Fol[iFol[u] + 2]);
  121. 					set.insert(Fol[iFol[v] + 0]);
  122. 					set.insert(Fol[iFol[v] + 1]);
  123. 					set.insert(Fol[iFol[v] + 2]);
  124.  
  125. 					if(set.find(u) == set.end())
  126. 					//nesousedi
  127. 					{
  128. 						if(set.size() >= 5)
  129. 						{
  130. 							printf("YES\n");
  131. 							goto NEXT_INSTANCE;
  132. 						}
  133. 					}
  134. 					else
  135. 					//sousedi
  136. 					{
  137. 						if(set.size() >= 6)
  138. 						{
  139. 							printf("YES\n");
  140. 							goto NEXT_INSTANCE;
  141. 						}
  142. 					}
  143. 				}
  144. 			}
  145. 		}
  146.  
  147. 		printf("NO\n");
  148. 		NEXT_INSTANCE:;
  149. 	}
  150.  
  151. 	return 0;
  152. }
  153.  

Diff to submission s929

fn.cpp

--- c5.s929.cteam091.fn.cpp.0.fn.cpp
+++ c5.s974.cteam091.fn.cpp.0.fn.cpp
@@ -82,4 +82,5 @@
                         QEnd = 0;
                         Q[QEnd++] = i;
+                        Visited[i] = 1;
                         
                         while(QBeg < QEnd)
@@ -100,7 +101,7 @@
                         for(int j = 0; j < QEnd; j++)
                         {
-                                if(Degree[Q[i]] == 3)
+                                if(Degree[Q[j]] == 3)
                                 {
-                                        List[nList++] = Q[i];
+                                        List[nList++] = Q[j];
                                 }
                         }
@@ -114,4 +115,5 @@
                                         
                                         SET set;
+                                        set.clear();
                                         set.insert(Fol[iFol[u] + 0]);
                                         set.insert(Fol[iFol[u] + 1]);