Source code for submission s669

Go to diff to previous submission

fn.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17.  
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25. const int INF = 1<<29;
  26.  
  27. typedef long long ll;
  28.  
  29. #define maxN 10005
  30.  
  31. int n,m;
  32. int x,y;
  33. vector<int> edges[maxN];
  34. bool found2;
  35. bool visited[maxN];
  36. bool diff;
  37. bool ok;
  38.  
  39. vector<int> th,paw;
  40.  
  41. void comp(int u){
  42. if(found2) return;
  43. if(visited[u]) return;
  44. visited[u]=true;
  45. if(edges[u].size()>=4) found2=true;
  46. if(edges[u].size()==3 && !found2){
  47. if(th.size()>=5){ found2=true; return; }
  48. REP(i,th.size()){
  49. diff = 0;
  50. REP(j,3){
  51. if(edges[th[i]][j]==u) continue;
  52. ok=true;
  53. REP(k,3){
  54. if(edges[th[i]][j]==edges[u][k]) ok=false;
  55. }
  56. if(ok) diff++;
  57. }
  58. if(diff>=2){ found2=true; break; }
  59. }
  60. th.push_back(u);
  61.  
  62. }
  63. REP(i,edges[u].size()){
  64. comp(edges[u][i]);
  65. }
  66. }
  67.  
  68. int main() {
  69. while(scanf("%d%d",&n,&m)==2){
  70. REP(i,n) edges[i].clear();
  71. REP(i,n) visited[i]=false;
  72. found2=false;
  73. REP(i,m){
  74. scanf("%d%d",&x,&y);
  75. x--; y--;
  76. edges[x].push_back(y);
  77. edges[y].push_back(x);
  78. }
  79. REP(i,n){
  80. th.clear();
  81. comp(i);
  82. }
  83. if(found2) printf("YES\n");
  84. else printf("NO\n");
  85.  
  86. }
  87.  
  88. return 0;
  89. }
  90.  

Diff to submission s640

fn.cpp

--- c5.s640.cteam010.fn.cpp.0.fn.cpp
+++ c5.s669.cteam010.fn.cpp.0.fn.cpp
@@ -40,8 +40,10 @@
 
 void comp(int u){
+        if(found2) return;
         if(visited[u]) return;
         visited[u]=true;
         if(edges[u].size()>=4) found2=true;
         if(edges[u].size()==3 && !found2){
+                if(th.size()>=5){ found2=true; return; }
                 REP(i,th.size()){
                         diff = 0;