Source code for submission s1029

Go to diff to previous submission

fn.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8.  
  9. using namespace std;
  10.  
  11. vector< vector<int> > G;
  12. bool marked[1000000];
  13. bool ok = false;
  14. vector<int> good;
  15. int visited;
  16.  
  17. void tam(int v)
  18. {
  19. visited++;
  20. marked[v] = true;
  21.  
  22. for(int i=0; i<G[v].size(); i++)
  23. {
  24. int u = G[v][i];
  25. if(marked[u])
  26. continue;
  27. tam(u);
  28. }
  29. }
  30.  
  31. void zpet(int v)
  32. {
  33. visited++;
  34. marked[v] = false;
  35.  
  36. for(int i=0; i<G[v].size(); i++)
  37. {
  38. int u = G[v][i];
  39. if(!marked[u])
  40. continue;
  41. zpet(u);
  42. }
  43. }
  44.  
  45. void dfs(int v)
  46. {
  47. if(G[v].size() >= 4)
  48. ok = true;
  49. else if(G[v].size() == 3)
  50. {
  51. //printf("test %d\n", v);
  52. for(int i=0; !ok && i<good.size(); i++)
  53. {
  54. int u = good[i];
  55.  
  56. //printf("%d %d\n", v, u);
  57.  
  58. set<int> s;
  59. for(int j=0; j<G[v].size(); j++)
  60. {
  61. if(G[v][j] != u)
  62. s.insert(G[v][j]);
  63. }
  64. for(int j=0; j<G[u].size(); j++)
  65. {
  66. if(G[u][j] != v)
  67. s.insert(G[u][j]);
  68. }
  69. if(s.size() >= 4)
  70. {
  71. ok = true;
  72. }
  73. }
  74. good.push_back(v);
  75. }
  76.  
  77. if(ok)
  78. return;
  79.  
  80. visited++;
  81. marked[v] = true;
  82.  
  83. for(int i=0; !ok && i< G[v].size(); i++)
  84. {
  85. int u = G[v][i];
  86. if(marked[u])
  87. continue;
  88. dfs(u);
  89. }
  90. }
  91.  
  92. int main()
  93. {
  94. int N, M;
  95. while(scanf("%d %d", &N, &M) == 2)
  96. {
  97. G = vector< vector<int> >(N);
  98. for(int i=0; i<N; i++)
  99. {
  100. G[i] = vector<int>();
  101. marked[i] = false;
  102. }
  103. for(int i=0; i<M; i++)
  104. {
  105. int x, y;
  106. scanf("%d %d", &x, &y);
  107. --x;
  108. --y;
  109. G[x].push_back(y);
  110. G[y].push_back(x);
  111. }
  112. ok = false;
  113. for(int i=0; !ok && i<N; i++)
  114. {
  115. visited = 0;
  116. good = vector<int>();
  117. if(!marked[i])
  118. {
  119. visited = 0;
  120. tam(i);
  121. //printf("tam from %d visited %d\n", i, visited);
  122. if(visited <= 4)
  123. {
  124. //printf("smula from %d visited %d\n", i, visited);
  125. continue;
  126. }
  127. visited = 0;
  128. zpet(i);
  129. //printf("zpet from %d visited %d\n", i, visited);
  130. visited = 0;
  131. dfs(i);
  132. //printf("dfs from %d visited %d\n", i, visited);
  133. }
  134. }
  135. if(!ok)
  136. puts("NO");
  137. else
  138. puts("YES");
  139. }
  140.  
  141. return 0;
  142. }
  143.  

Diff to submission s819

fn.cpp

--- c5.s819.cteam036.fn.cpp.0.fn.cpp
+++ c5.s1029.cteam036.fn.cpp.0.fn.cpp
@@ -12,7 +12,35 @@
 bool marked[1000000];
 bool ok = false;
-int good;
+vector<int> good;
 int visited;
 
+void tam(int v)
+{
+        visited++;
+        marked[v] = true;
+
+        for(int i=0; i<G[v].size(); i++)
+        {
+                int u = G[v][i];
+                if(marked[u])
+                        continue;
+                tam(u);
+        }
+}
+
+void zpet(int v)
+{
+        visited++;
+        marked[v] = false;
+
+        for(int i=0; i<G[v].size(); i++)
+        {
+                int u = G[v][i];
+                if(!marked[u])
+                        continue;
+                zpet(u);
+        }
+}
+
 void dfs(int v)
 {
@@ -20,10 +48,38 @@
                 ok = true;
         else if(G[v].size() == 3)
-                good++;
+        {
+                //printf("test %d\n", v);
+                for(int i=0; !ok && i<good.size(); i++)
+                {
+                        int u = good[i];
+                        
+                        //printf("%d %d\n", v, u);
+                        
+                        set<int> s;
+                        for(int j=0; j<G[v].size(); j++)
+                        {
+                                if(G[v][j] != u)
+                                        s.insert(G[v][j]);
+                        }
+                        for(int j=0; j<G[u].size(); j++)
+                        {
+                                if(G[u][j] != v)
+                                        s.insert(G[u][j]);
+                        }
+                        if(s.size() >= 4)
+                        {
+                                ok = true;
+                        }
+                }
+                good.push_back(v);
+        }
+        
+        if(ok)
+                return;
         
         visited++;
         marked[v] = true;
 
-        for(int i=0; i<G[v].size(); i++)
+        for(int i=0; !ok && i< G[v].size(); i++)
         {
                 int u = G[v][i];
@@ -58,9 +114,22 @@
                 {
                         visited = 0;
-                        good = 0;
+                        good = vector<int>();
                         if(!marked[i])
+                        {
+                                visited = 0;
+                                tam(i);
+                                //printf("tam from %d visited %d\n", i, visited);
+                                if(visited <= 4)
+                                {
+                                        //printf("smula from %d visited %d\n", i, visited);
+                                        continue;
+                                }
+                                visited = 0;
+                                zpet(i);
+                                //printf("zpet from %d visited %d\n", i, visited);
+                                visited = 0;
                                 dfs(i);
-                        if(good >= 2 && visited >= 5)
-                                ok = true;
+                                //printf("dfs from %d visited %d\n", i, visited);
+                        }
                 }
                 if(!ok)