Source code for submission s841

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. #include<set>
  10.  
  11. using namespace std;
  12.  
  13. #define FOR(i,a,b) for(int i=a; i<=b; i++)
  14.  
  15. #define PII pair<int, int>
  16. #define MP make_pair
  17. #define PB push_back
  18.  
  19. #define SIZE(s) ((int)(s).size())
  20. #define FOREACH(obj, it) for(__typeof(obj.begin()) it = (obj).begin(); it != (obj).end(); (it)++)
  21.  
  22. #define ll long long
  23.  
  24. #define MAX 10047
  25.  
  26. int N, M;
  27. vector<int> G[MAX];
  28.  
  29. int colors[MAX];
  30. int color;
  31.  
  32. void dfs(int v)
  33. {
  34. colors[v] = color;
  35. FOR(i,0, SIZE(G[v])-1)
  36. {
  37. int u = G[v][i];
  38. if (colors[u] == 0)
  39. dfs(u);
  40. }
  41. }
  42.  
  43. int V[MAX];
  44.  
  45. int st4[MAX];
  46. vector<int> st3[MAX];
  47.  
  48. bool skus2(int zly, int v)
  49. {
  50. FOR(i,0,SIZE(G[v])-1)
  51. {
  52. if (G[v][i] == zly) return false;
  53. }
  54. return true;
  55. }
  56.  
  57. //skusime medzi dvoma vrcholmi
  58. bool skus(int v1, int v2)
  59. {
  60. // cout << v1 << " " << v2 << endl;
  61. set<int> vrchols;
  62. FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2 && skus2(G[v1][i], v2)) vrchols.insert( G[v1][i] );
  63. FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1 && skus2(G[v2][i], v1)) vrchols.insert( G[v2][i] );
  64. return SIZE(vrchols) >= 4;
  65. }
  66.  
  67. int main()
  68. {
  69. int a, b;
  70. while(scanf("%d %d",&N, &M)== 2)
  71. {
  72. FOR(i,0,N-1) G[i].clear();
  73. FOR(i,0,N-1) V[i] = 0;
  74. while(M--)
  75. {
  76. scanf("%d %d",&a,&b);
  77. a--; b--;
  78. G[a].PB(b);
  79. G[b].PB(a);
  80. V[a]++;
  81. V[b]++;
  82. }
  83.  
  84. color = 0;
  85. FOR(i,0,N-1) colors[i] = 0;
  86. FOR(i,0,N-1)
  87. {
  88. if (colors[i] == 0)
  89. {
  90. color++;
  91. dfs(i);
  92. }
  93. }
  94.  
  95. // FOR(i,0,N-1) cout << colors[i] << endl;
  96.  
  97. bool ok = false;
  98. FOR(c,1,color)
  99. {
  100. st4[c] = 0;
  101. st3[c].clear();
  102. }
  103. FOR(i,0,N-1)
  104. {
  105. if (V[i] > 3)
  106. st4[ colors[i] ]++;
  107. if (V[i] > 2)
  108. st3[ colors[i] ].PB(i);
  109. }
  110.  
  111. FOR(c,1,color)
  112. {
  113. if (st4[c] >= 1)
  114. {
  115. ok = true;
  116. break;
  117. }
  118. if (SIZE(st3[c]) > 1)
  119. {
  120. FOR(i,0, SIZE( st3[c])-2)
  121. FOR(j, i+1 , SIZE(st3[c])-1)
  122. {
  123. if (skus( st3[c][i], st3[c][j]))
  124. {
  125. // cout << st3[c][i]+1 << " " << st3[c][j]+1 << endl;
  126. ok = true;
  127. break;
  128. }
  129. }
  130. }
  131. }
  132.  
  133. if (ok) puts("YES");
  134. else puts("NO");
  135. }
  136. return 0;
  137. }
  138.  
  139.  

Diff to submission s753

fn.cpp

--- c5.s753.cteam079.fn.cpp.0.fn.cpp
+++ c5.s841.cteam079.fn.cpp.0.fn.cpp
@@ -18,4 +18,5 @@
 
 #define SIZE(s) ((int)(s).size())
+#define FOREACH(obj, it) for(__typeof(obj.begin()) it = (obj).begin(); it != (obj).end(); (it)++)
 
 #define ll long long
@@ -45,4 +46,13 @@
 vector<int> st3[MAX];
 
+bool skus2(int zly, int v)
+{
+        FOR(i,0,SIZE(G[v])-1)
+        {
+                if (G[v][i] == zly) return false;
+        }
+        return true;
+}
+
 //skusime medzi dvoma vrcholmi
 bool skus(int v1, int v2)
@@ -50,6 +60,6 @@
 //      cout << v1 << " " << v2 << endl;
         set<int> vrchols;
-        FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2) vrchols.insert( G[v1][i] );
-        FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1) vrchols.insert( G[v2][i] );
+        FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2 && skus2(G[v1][i], v2)) vrchols.insert( G[v1][i] );
+        FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1 && skus2(G[v2][i], v1)) vrchols.insert( G[v2][i] );
         return SIZE(vrchols) >= 4;
 }
@@ -108,9 +118,10 @@
                         if (SIZE(st3[c]) > 1)
                         {
-                                FOR(i,0, SIZE( st3[c])-1)
+                                FOR(i,0, SIZE( st3[c])-2)
                                         FOR(j, i+1 , SIZE(st3[c])-1)
                                         {
                                                 if (skus( st3[c][i], st3[c][j])) 
                                                 {
+                                                //      cout << st3[c][i]+1 << " " << st3[c][j]+1 << endl;
                                                         ok = true;
                                                         break;