Source code for submission s1068

Go to diff to previous submission

fn.cpp

  1. #include <cstdio>
  2. #include <vector>
  3. #include <iostream>
  4. #include <string>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <set>
  8. #include <vector>
  9.  
  10. using namespace std;
  11.  
  12. vector<vector<int> > arr;
  13. vector<vector<int> > kom;
  14. vector<int> comp;
  15.  
  16. void go(int a, int c)
  17. {
  18. comp[a] = c;
  19. for (int i = 0; i < arr[a].size(); ++i)
  20. if (comp[arr[a][i]] == -1)
  21. go(arr[a][i], c);
  22. }
  23.  
  24. bool intersect(int a, int b)
  25. {
  26. int end = 6;
  27. set<int> s;
  28. s.insert(a);
  29. s.insert(b);
  30.  
  31. for (int i = 0; i < arr[a].size(); ++i)
  32. {
  33. s.insert(arr[a][i]);
  34. if (arr[a][i] == b)
  35. ++end;
  36. }
  37.  
  38. for (int i = 0; i < arr[b].size(); ++i)
  39. {
  40. s.insert(arr[b][i]);
  41. if (arr[b][i] == a)
  42. ++end;
  43. }
  44. // cout << end << endl;
  45. return s.size() >= end;
  46. }
  47.  
  48. int main()
  49. {
  50. int N,M,x,y,i;
  51.  
  52.  
  53.  
  54. while (scanf("%d %d\n",&N,&M) > 0)
  55. {
  56. bool ans = false;
  57. arr.clear();
  58. arr.resize(N+1);
  59. comp.clear();
  60. comp.resize(N+1, -1);
  61. kom.clear();
  62.  
  63. for(i=1;i<=M;i++)
  64. {
  65. scanf("%d %d\n",&x,&y);
  66.  
  67. arr[x].push_back(y);
  68. arr[y].push_back(x);
  69. if (arr[x].size() >= 4 || arr[y].size() >= 4)
  70. { ans = true; }
  71. }
  72.  
  73. if (!ans)
  74. {
  75. int cc = 1;
  76. for (int i = 1; i <= N; ++i)
  77. {
  78. if (comp[i] == -1)
  79. go(i, cc++);
  80. }
  81.  
  82. kom.resize(cc);
  83. // cout << "kom " << cc << endl;
  84. for (int i = 1; i <= N; ++i)
  85. {
  86. if (arr[i].size() > 2)
  87. kom[comp[i]].push_back(i);
  88. }
  89.  
  90. for (int i = 0; !ans && i < kom.size(); ++i)
  91. {
  92. vector<int>& tmp = kom[i];
  93.  
  94. for (int j = 0; !ans && j < tmp.size(); ++j)
  95. for (int k = j+1; !ans && k < tmp.size(); ++k)
  96. if (intersect(tmp[j], tmp[k]))
  97. {
  98. ans = true;
  99. //cout << "match " << tmp[j] << " " << tmp[k] << endl;
  100. }
  101. }
  102. }
  103.  
  104. if (ans)
  105. printf("YES\n");
  106. else
  107. printf("NO\n");
  108. }
  109.  
  110. return 0;
  111. }
  112.  

Diff to submission s996

fn.cpp

--- c5.s996.cteam078.fn.cpp.0.fn.cpp
+++ c5.s1068.cteam078.fn.cpp.0.fn.cpp
@@ -24,4 +24,5 @@
 bool intersect(int a, int b)
 {
+    int end = 6;
     set<int> s;
     s.insert(a);
@@ -27,11 +28,20 @@
     s.insert(a);
     s.insert(b);
+
     for (int i = 0; i < arr[a].size(); ++i)
+    {
         s.insert(arr[a][i]);
+        if (arr[a][i] == b)
+            ++end;
+    }
 
     for (int i = 0; i < arr[b].size(); ++i)
+    {
         s.insert(arr[b][i]);
-
-    return s.size() >= 6;
+        if (arr[b][i] == a)
+            ++end;
+    }
+//    cout << end <<  endl;
+    return s.size() >= end;
 }
 
@@ -87,5 +97,5 @@
                    {
                      ans = true; 
-                   //cout << "match " << tmp[j] << " " << tmp[k] << endl;
+                 //cout << "match " << tmp[j] << " " << tmp[k] << endl;
                     }
         }