Source code for submission s971

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.     set<int> s;
  27.     s.insert(a);
  28.     s.insert(b);
  29.     for (int i = 0; i < arr[a].size(); ++i)
  30.         s.insert(arr[a][i]);
  31.  
  32.     for (int i = 0; i < arr[b].size(); ++i)
  33.         s.insert(arr[b][i]);
  34.  
  35.     return s.size() >= 6;
  36. }
  37.  
  38. int main()
  39. {
  40. int N,M,x,y,i;
  41.  
  42.  
  43.  
  44. while (scanf("%d %d\n",&N,&M) > 0)
  45. {
  46.     bool ans = false;
  47.     arr.clear();
  48.     arr.resize(N+1);
  49.     comp.clear();
  50.     comp.resize(N+1, -1);
  51.  
  52.    for(i=1;i<=M;i++)
  53.    {
  54.     scanf("%d %d\n",&x,&y); 
  55.  
  56.     arr[x].push_back(y);
  57.     arr[y].push_back(x);
  58.     if (arr[x].size() >= 4 || arr[y].size() >= 4)
  59.             {  ans = true; }
  60.     }  
  61.  
  62.     if (!ans)
  63.     {
  64.         int cc = 1;
  65.         for (int i = 1; i <= N; ++i)
  66.         {
  67.             if (comp[i] == -1)
  68.                 go(i, cc++);
  69.         }
  70.  
  71.         kom.resize(cc);
  72. //        cout << "kom " << cc << endl;
  73.         for (int i = 1; i <= N; ++i)
  74.         {
  75.             if (arr[i].size() > 2)
  76.                 kom[comp[i]].push_back(i);
  77.         }
  78.  
  79.         for (int i = 0; !ans && i < kom.size(); ++i)
  80.         {
  81.             vector<int>& tmp = kom[i];
  82.  
  83.             for (int j = 0; !ans && j < tmp.size(); ++j)
  84.                 for (int k = j+1; !ans && k < tmp.size(); ++k)
  85.                    if (intersect(tmp[j], tmp[k]))
  86.                    {
  87.                      ans = true; 
  88.                    //cout << "match " << tmp[j] << " " << tmp[k] << endl;
  89.                     }
  90.         }
  91.     }
  92.  
  93.     if (ans)
  94.         printf("YES\n");
  95.     else
  96.         printf("NO\n");
  97. }
  98.  
  99. return 0;
  100. }
  101.  

Diff to submission s955

fn.cpp

--- c5.s955.cteam078.fn.cpp.0.fn.cpp
+++ c5.s971.cteam078.fn.cpp.0.fn.cpp
@@ -22,14 +22,16 @@
 }
 
-bool intersect(vector<int>& a, vector<int>& b)
+bool intersect(int a, int b)
 {
     set<int> s;
-    for (int i = 0; i < a.size(); ++i)
-        s.insert(a[i]);
+    s.insert(a);
+    s.insert(b);
+    for (int i = 0; i < arr[a].size(); ++i)
+        s.insert(arr[a][i]);
 
-    for (int i = 0; i < b.size(); ++i)
-        s.insert(b[i]);
+    for (int i = 0; i < arr[b].size(); ++i)
+        s.insert(arr[b][i]);
 
-    return s.size() >= 4;
+    return s.size() >= 6;
 }
 
@@ -81,6 +83,9 @@
             for (int j = 0; !ans && j < tmp.size(); ++j)
                 for (int k = j+1; !ans && k < tmp.size(); ++k)
-                   if (intersect(arr[tmp[j]], arr[tmp[k]]))
+                   if (intersect(tmp[j], tmp[k]))
+                   {
                      ans = true; 
+                   //cout << "match " << tmp[j] << " " << tmp[k] << endl;
+                    }
         }
     }