Source code for submission s528

Go to diff to previous submission

fn.cpp

  1. #include<iostream>
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<ctype.h>
  6. #include<math.h>
  7.  
  8. #include<vector>
  9.  
  10. using namespace std;
  11.  
  12. #define FOR(i,a,b) for(int i=a; i<=b; i++)
  13.  
  14. #define PII pair<int, int>
  15. #define MP make_pair
  16. #define PB push_back
  17.  
  18. #define SIZE(s) ((int)(s).size())
  19.  
  20. #define ll long long
  21.  
  22. #define MAX 10047
  23.  
  24. int N, M;
  25. vector<int> G[MAX];
  26.  
  27. int colors[MAX];
  28. int color;
  29.  
  30. void dfs(int v)
  31. {
  32. 	colors[v] = color;
  33. 	FOR(i,0, SIZE(G[v])-1)
  34. 	{
  35. 		int u = G[v][i];
  36. 		if (colors[u] == 0)
  37. 			dfs(u);
  38. 	}
  39. }
  40.  
  41. int V[MAX];
  42.  
  43. int st4[MAX];
  44. int st3[MAX];
  45.  
  46. int main()
  47. {
  48. 	int a, b;
  49. 	while(scanf("%d %d",&N, &M)== 2)
  50. 	{
  51. 		FOR(i,0,N-1) G[i].clear();
  52. 		FOR(i,0,N-1) V[i] = 0;
  53. 		while(M--)
  54. 		{
  55. 			scanf("%d %d",&a,&b);
  56. 			a--; b--;
  57. 			G[a].PB(b);
  58. 			G[b].PB(a);
  59. 			V[a]++;
  60. 			V[b]++;
  61. 		}
  62.  
  63. 		color = 0;
  64. 		FOR(i,0,N-1) colors[i] = 0;
  65. 		FOR(i,0,N-1)
  66. 		{
  67. 			if (colors[i] == 0)
  68. 			{
  69. 				color++;
  70. 				dfs(i);
  71. 			}
  72. 		}
  73.  
  74. 	//	FOR(i,0,N-1) cout << colors[i] << endl;
  75.  
  76. 		bool ok = false;
  77. 		FOR(c,1,color)
  78. 		{
  79. 			st4[c] = 0;
  80. 			st3[c] = 0;			
  81. 		}
  82. 		FOR(i,0,N-1)
  83. 		{
  84. 			if (V[i] > 3)
  85. 				st4[ colors[i] ]++;
  86. 			if (V[i] > 2)
  87. 				st3[ colors[i] ]++;
  88. 		}
  89.  
  90. 		FOR(c,1,color)
  91. 		{
  92. 			if (st4[c] >= 1) ok = true;
  93. 			if (st3[c] >= 2) ok = true;
  94. 		}
  95.  
  96. 		if (ok) puts("YES");
  97. 		else puts("NO");
  98. 	}
  99. 	return 0;
  100. }
  101.  
  102.  

Diff to submission s470

fn.cpp

--- c5.s470.cteam079.fn.cpp.0.fn.cpp
+++ c5.s528.cteam079.fn.cpp.0.fn.cpp
@@ -16,5 +16,5 @@
 #define PB push_back
 
-#define SIZE(s) (int)(s).int()
+#define SIZE(s) ((int)(s).size())
 
 #define ll long long
@@ -22,6 +22,25 @@
 #define MAX 10047
 
-int V[MAX];
 int N, M;
+vector<int> G[MAX];
+
+int colors[MAX];
+int color;
+
+void dfs(int v)
+{
+        colors[v] = color;
+        FOR(i,0, SIZE(G[v])-1)
+        {
+                int u = G[v][i];
+                if (colors[u] == 0)
+                        dfs(u);
+        }
+}
+
+int V[MAX];
+
+int st4[MAX];
+int st3[MAX];
 
 int main()
@@ -30,4 +49,5 @@
         while(scanf("%d %d",&N, &M)== 2)
         {
+                FOR(i,0,N-1) G[i].clear();
                 FOR(i,0,N-1) V[i] = 0;
                 while(M--)
@@ -35,14 +55,43 @@
                         scanf("%d %d",&a,&b);
                         a--; b--;
+                        G[a].PB(b);
+                        G[b].PB(a);
                         V[a]++;
                         V[b]++;
                 }
 
+                color = 0;
+                FOR(i,0,N-1) colors[i] = 0;
+                FOR(i,0,N-1)
+                {
+                        if (colors[i] == 0)
+                        {
+                                color++;
+                                dfs(i);
+                        }
+                }
+
+        //      FOR(i,0,N-1) cout << colors[i] << endl;
+
                 bool ok = false;
+                FOR(c,1,color)
+                {
+                        st4[c] = 0;
+                        st3[c] = 0;                     
+                }
                 FOR(i,0,N-1)
                 {
-                        if (V[i] >= 4) ok = true;
+                        if (V[i] > 3)
+                                st4[ colors[i] ]++;
+                        if (V[i] > 2)
+                                st3[ colors[i] ]++;
                 }
 
+                FOR(c,1,color)
+                {
+                        if (st4[c] >= 1) ok = true;
+                        if (st3[c] >= 2) ok = true;
+                }
+                
                 if (ok) puts("YES");
                 else puts("NO");