Source code for submission s805

Go to diff to previous submission

furry.cpp

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <limits.h>
  8. #include <map>
  9. #include <queue>
  10. #include <vector>
  11. #include <set>
  12. #include <stack>
  13. #include <bitset>
  14. #include <string>
  15.  
  16. using namespace std;
  17.  
  18. typedef pair<int,int> ii;
  19. typedef vector<int> vi;
  20. typedef vector<ii> vii;
  21. typedef set<int> si;
  22. typedef set<ii> sii;
  23.  
  24. #define MP make_pair
  25. #define PB push_back
  26. #define REP(i,a) for ( int i = 0; i < int(a); i++)
  27. #define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++)
  28. #define FORD(i,a,b) for(int i= int(a); i>=int(b); i--)
  29.  
  30. const int INF = 1<<29;
  31. typedef long long int ll;
  32.  
  33. int gn[10001][10001];
  34. int gc[10001];
  35. int is[10001];
  36. int con[10001];
  37. int num,n;
  38. int tree,four,ones;
  39.  
  40. void dfs(int x){
  41. int xx;
  42.  
  43. //cout << num << endl;
  44. is[x] = 1;
  45. //if (gc[x] >= 4) four++;
  46. //if (gc[x] >= 3) tree++;
  47. if (gc[x] == 1) ones++;
  48. REP(i,gc[x]){
  49. xx = gn[x][i];
  50. if( !is[xx] ){
  51. dfs(xx);
  52. }
  53.  
  54.  
  55. }
  56.  
  57. }
  58.  
  59. bool solve(){
  60. REP(i,n){
  61. if(con[i] && !is[i]){
  62. tree = four = ones = 0;
  63. dfs(i);
  64. //if ( four > 0 || tree > 1)return true;
  65. if(ones == 4)return true;
  66. }
  67. }
  68.  
  69.  
  70. return false;
  71. }
  72.  
  73.  
  74. int main(){
  75. int m,x,y;
  76. while ( scanf("%d%d",&n,&m) == 2){
  77. memset(gc,0,sizeof gc);
  78. memset(is,0,sizeof is);
  79. memset(con,0,sizeof con);
  80. REP(i,m){scanf("%d%d",&x,&y);
  81. gn[x][gc[x]++] = y;
  82. gn[y][gc[y]++] = x;
  83. con[x] = 1;
  84. con[y] = 1;
  85. }
  86. if ( solve() ) printf("YES\n");
  87. else printf("NO\n");
  88.  
  89.  
  90. };
  91.  
  92.  
  93.  
  94. return 0;
  95. }
  96.  
  97.  

Diff to submission s796

furry.cpp

--- c5.s796.cteam013.fn.cpp.0.furry.cpp
+++ c5.s805.cteam013.fn.cpp.0.furry.cpp
@@ -36,5 +36,5 @@
 int con[10001];
 int num,n;
-int tree,four;
+int tree,four,ones;
 
 void dfs(int x){
@@ -43,7 +43,7 @@
 //cout << num << endl;
         is[x] = 1;
-        if (gc[x] >= 4) four++;
-        if (gc[x] >= 3) tree++;
-                
+        //if (gc[x] >= 4) four++;
+        //if (gc[x] >= 3) tree++;
+        if (gc[x] == 1) ones++; 
         REP(i,gc[x]){
                 xx = gn[x][i];
@@ -60,7 +60,8 @@
         REP(i,n){
                 if(con[i] && !is[i]){
-                        tree = four = 0;                        
+                        tree = four = ones = 0;                 
                         dfs(i);                 
-                        if ( four > 0 || tree > 1)return true;
+                        //if ( four > 0 || tree > 1)return true;
+                        if(ones == 4)return true;
                 }
         }