Source code for submission s989

Go to diff to previous submission

fn.cpp

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <string>
  8. #include <deque>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <stack>
  14. #include <vector>
  15. using namespace std;
  16.  
  17. #define debug printf
  18. //#define debug blackhole
  19. void blackhole(...) {}
  20.  
  21. #define MAXN 20000
  22. int ADJ_N[MAXN];
  23. int V;
  24. int E;
  25. int Vp[MAXN];
  26. int Ep[MAXN];
  27. int fir[MAXN];
  28. int sec[MAXN];
  29. int comp[MAXN];
  30. int compcnt;
  31. int Q[2*MAXN];
  32. int Qsize;
  33. int GoodInComp[MAXN];
  34. int used[MAXN];
  35.  
  36. bool walk(int component) {
  37. for (int i = 0; i < V; i++) {
  38. if (comp[i] != component || ADJ_N[i] < 3)
  39. continue;
  40. for (int j = 0; j < V; j++)
  41. used[j] = 0;
  42. Qsize = 0;
  43. int leavecnt = 0;
  44. Q[Qsize++] = i;
  45. used[i] = 1;
  46. for (int q = 0; q < Qsize; q++) {
  47. int isleave = 1;
  48. for (int v = Vp[Q[q]]; v < Vp[Q[q]+1]; v++) {
  49. if (used[Ep[v]] == 0) {
  50. isleave = 0;
  51. used[Ep[v]] = 1;
  52. Q[Qsize++] = Ep[v];
  53. }
  54.  
  55. }
  56. if (isleave == 1) {
  57. leavecnt++;
  58. }
  59. }
  60. if (leavecnt >= 4)
  61. return true;
  62. }
  63. return false;
  64. }
  65.  
  66.  
  67. void GO() {
  68.  
  69. for (int i = 0; i < MAXN; i++) {
  70. Vp[i] = 0;
  71. Ep[i] = 0;
  72. fir[i] = sec[i] = 0;
  73. Qsize = 0;
  74. Q[i] = 0;
  75. GoodInComp[i] = 0;
  76. comp[i] = 0;
  77. compcnt = 0;
  78. ADJ_N[i] = 0;
  79. }
  80.  
  81. for (int i = 0; i < E; i++) {
  82.  
  83. scanf("%d%d", fir+i, sec+i);
  84. Vp[--fir[i]]++;
  85. Vp[--sec[i]]++;
  86. ADJ_N[fir[i]]++;
  87. ADJ_N[sec[i]]++;
  88. }
  89. for (int i = 0; i < V; i++)
  90. Vp[i+1] += Vp[i];
  91. for (int i = 0; i < E; i++) {
  92. Ep[--Vp[fir[i]]] = sec[i];
  93. Ep[--Vp[sec[i]]] = fir[i];
  94. }
  95.  
  96. int qq;
  97. for (qq=0;qq<V;qq++) {
  98. if (ADJ_N[qq] >= 4){
  99. printf("YES\n");
  100. return;
  101. }
  102. }
  103.  
  104. int max = 0;
  105. for (int i = 0; i < V; i++) {
  106. if (ADJ_N[i] > max)
  107. max = ADJ_N[i];
  108. }
  109. if (max <= 2) {
  110. printf("NO\n");
  111. return;
  112. }
  113.  
  114. for (int i = 0; i < V; i++) {
  115. if (comp[i] > 0)
  116. continue;
  117. comp[i] = ++compcnt;
  118. Qsize = 0;
  119. Q[Qsize++] = i;
  120. for (int q = 0; q < Qsize; q++) {
  121. for (int v = Vp[Q[q]]; v < Vp[Q[q]+1]; v++) {
  122. if (comp[Ep[v]] == 0) {
  123. comp[Ep[v]] = compcnt;
  124. Q[Qsize++] = Ep[v];
  125. }
  126. }
  127. }
  128. }
  129.  
  130. for (int i = 0; i < V; i++) {
  131. if (ADJ_N[i] >= 3) {
  132. GoodInComp[comp[i]]++;
  133. }
  134. }
  135. for (int i = 1; i <= compcnt; i++) {
  136. if (GoodInComp[comp[i]] > 5) {
  137. printf("YES\n");
  138. return;
  139. }
  140. if (GoodInComp[comp[i]] >= 2) {
  141. if (walk(i)) {
  142. printf("YES\n");
  143. return;
  144. }
  145. }
  146. }
  147.  
  148. printf("NO\n");
  149.  
  150. }
  151.  
  152. int main() {
  153. while (true) {
  154. if (scanf("%d%d", &V, &E) != 2) break;
  155. GO();
  156. }
  157. return 0;
  158. }
  159.  

Diff to submission s660

fn.cpp

--- c5.s660.cteam032.fn.cpp.0.fn.cpp
+++ c5.s989.cteam032.fn.cpp.0.fn.cpp
@@ -1,3 +1,4 @@
 #include <cstdio>
+#include <iostream>
 #include <cstdlib>
 #include <cmath>
@@ -31,4 +32,36 @@
 int Qsize;
 int GoodInComp[MAXN];
+int used[MAXN];
+
+bool walk(int component) {
+        for (int i = 0; i < V; i++) {
+                if (comp[i] != component || ADJ_N[i] < 3)
+                        continue;
+                for (int j = 0; j < V; j++)
+                        used[j] = 0;
+                Qsize = 0;
+                int leavecnt = 0;
+                Q[Qsize++] = i;
+                used[i] = 1;
+                for (int q = 0; q < Qsize; q++) {
+                        int isleave = 1;
+                        for (int v = Vp[Q[q]]; v < Vp[Q[q]+1]; v++) {
+                                if (used[Ep[v]] == 0) {
+                                        isleave = 0;
+                                        used[Ep[v]] = 1;
+                                        Q[Qsize++] = Ep[v];
+                                }
+                                
+                        }
+                        if (isleave == 1) {
+                                leavecnt++;
+                        }
+                }
+                if (leavecnt >= 4)
+                        return true;
+        }
+        return false;
+}
+
 
 void GO() {
@@ -100,8 +134,14 @@
         }
         for (int i = 1; i <= compcnt; i++) {
-                if (GoodInComp[comp[i]] >= 2) {
+                if (GoodInComp[comp[i]] > 5) {
                         printf("YES\n");
                         return;
                 }
+                if (GoodInComp[comp[i]] >= 2) {
+                        if (walk(i)) {
+                                printf("YES\n");
+                                return;
+                        }
+                }
         }