Source code for submission s660

Go to diff to previous submission

fn.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <string>
  7. #include <deque>
  8. #include <list>
  9. #include <map>
  10. #include <queue>
  11. #include <set>
  12. #include <stack>
  13. #include <vector>
  14. using namespace std;
  15.  
  16. #define debug printf
  17. //#define debug blackhole
  18. void blackhole(...) {}
  19.  
  20. #define MAXN 20000
  21. int ADJ_N[MAXN];
  22. int V;
  23. int E;
  24. int Vp[MAXN];
  25. int Ep[MAXN];
  26. int fir[MAXN];
  27. int sec[MAXN];
  28. int comp[MAXN];
  29. int compcnt;
  30. int Q[2*MAXN];
  31. int Qsize;
  32. int GoodInComp[MAXN];
  33.  
  34. void GO() {
  35.  
  36. for (int i = 0; i < MAXN; i++) {
  37. Vp[i] = 0;
  38. Ep[i] = 0;
  39. fir[i] = sec[i] = 0;
  40. Qsize = 0;
  41. Q[i] = 0;
  42. GoodInComp[i] = 0;
  43. comp[i] = 0;
  44. compcnt = 0;
  45. ADJ_N[i] = 0;
  46. }
  47.  
  48. for (int i = 0; i < E; i++) {
  49. scanf("%d%d", fir+i, sec+i);
  50. Vp[--fir[i]]++;
  51. Vp[--sec[i]]++;
  52. ADJ_N[fir[i]]++;
  53. ADJ_N[sec[i]]++;
  54. }
  55. for (int i = 0; i < V; i++)
  56. Vp[i+1] += Vp[i];
  57. for (int i = 0; i < E; i++) {
  58. Ep[--Vp[fir[i]]] = sec[i];
  59. Ep[--Vp[sec[i]]] = fir[i];
  60. }
  61.  
  62. int qq;
  63. for (qq=0;qq<V;qq++) {
  64. if (ADJ_N[qq] >= 4){
  65. printf("YES\n");
  66. return;
  67. }
  68. }
  69.  
  70. int max = 0;
  71. for (int i = 0; i < V; i++) {
  72. if (ADJ_N[i] > max)
  73. max = ADJ_N[i];
  74. }
  75. if (max <= 2) {
  76. printf("NO\n");
  77. return;
  78. }
  79.  
  80. for (int i = 0; i < V; i++) {
  81. if (comp[i] > 0)
  82. continue;
  83. comp[i] = ++compcnt;
  84. Qsize = 0;
  85. Q[Qsize++] = i;
  86. for (int q = 0; q < Qsize; q++) {
  87. for (int v = Vp[Q[q]]; v < Vp[Q[q]+1]; v++) {
  88. if (comp[Ep[v]] == 0) {
  89. comp[Ep[v]] = compcnt;
  90. Q[Qsize++] = Ep[v];
  91. }
  92. }
  93. }
  94. }
  95.  
  96. for (int i = 0; i < V; i++) {
  97. if (ADJ_N[i] >= 3) {
  98. GoodInComp[comp[i]]++;
  99. }
  100. }
  101. for (int i = 1; i <= compcnt; i++) {
  102. if (GoodInComp[comp[i]] >= 2) {
  103. printf("YES\n");
  104. return;
  105. }
  106. }
  107.  
  108. printf("NO\n");
  109.  
  110. }
  111.  
  112. int main() {
  113. while (true) {
  114. if (scanf("%d%d", &V, &E) != 2) break;
  115. GO();
  116. }
  117. return 0;
  118. }
  119.  

Diff to submission s552

fn.cpp

--- c5.s552.cteam032.fn.cpp.0.fn.cpp
+++ c5.s660.cteam032.fn.cpp.0.fn.cpp
@@ -22,14 +22,40 @@
 int V;
 int E;
+int Vp[MAXN];
+int Ep[MAXN];
+int fir[MAXN];
+int sec[MAXN];
+int comp[MAXN];
+int compcnt;
+int Q[2*MAXN];
+int Qsize;
+int GoodInComp[MAXN];
 
 void GO() {
-        for (int i=0;i<MAXN;i++) {
-                ADJ_N[i]=0;
+
+        for (int i = 0; i < MAXN; i++) {
+                Vp[i] = 0;
+                Ep[i] = 0;
+                fir[i] = sec[i] = 0;
+                Qsize = 0;
+                Q[i] = 0;
+                GoodInComp[i] = 0;
+                comp[i] = 0;
+                compcnt = 0;
+                ADJ_N[i] = 0;
         }
+
         for (int i = 0; i < E; i++) {
-                int a, b;
-                scanf("%d%d", &a, &b);
-                ADJ_N[a]++;
-                ADJ_N[b]++;
+                scanf("%d%d", fir+i, sec+i);
+                Vp[--fir[i]]++;
+                Vp[--sec[i]]++;
+                ADJ_N[fir[i]]++;
+                ADJ_N[sec[i]]++;
+        }
+        for (int i = 0; i < V; i++)
+                Vp[i+1] += Vp[i];
+        for (int i = 0; i < E; i++) {
+                Ep[--Vp[fir[i]]] = sec[i];
+                Ep[--Vp[sec[i]]] = fir[i];
         }
 
@@ -38,8 +64,48 @@
                 if (ADJ_N[qq] >= 4){
                         printf("YES\n");
-                        break;
+                        return;
                 }
         }
-        if (qq==V) printf("NO\n");
+        
+        int max = 0;
+        for (int i = 0; i < V; i++) {
+                if (ADJ_N[i] > max)
+                        max = ADJ_N[i];
+        }
+        if (max <= 2) {
+                printf("NO\n");
+                return;
+        }
+
+        for (int i = 0; i < V; i++) {
+                if (comp[i] > 0)
+                        continue;
+                comp[i] = ++compcnt;
+                Qsize = 0;
+                Q[Qsize++] = i;
+                for (int q = 0; q < Qsize; q++) {
+                        for (int v = Vp[Q[q]]; v < Vp[Q[q]+1]; v++) {
+                                if (comp[Ep[v]] == 0) {
+                                        comp[Ep[v]] = compcnt;
+                                        Q[Qsize++] = Ep[v];
+                                }
+                        }
+                }
+        }
+
+        for (int i = 0; i < V; i++) {
+                if (ADJ_N[i] >= 3) {
+                        GoodInComp[comp[i]]++;
+                }
+        }
+        for (int i = 1; i <= compcnt; i++) {
+                if (GoodInComp[comp[i]] >= 2) {
+                        printf("YES\n");
+                        return;
+                }
+        }
+
+        printf("NO\n");
+
 }