Source code for submission s1002

Go to diff to previous submission

fn.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include<cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <string>
  13. #include <vector>
  14.  
  15. using namespace std;
  16.  
  17. #define REP(i,n) for ( int i = 0; i < (n); i++)
  18. #define FOR(i,a,b) for ( int i = (a); i <= (b); i++ )
  19. #define FORD(i,a,b) for ( int i = (a); i>= (b); i-- )
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21.  
  22. bool bunny;
  23. int grade[10024];
  24. bool visited [10024];
  25. int sib[10024][10024];
  26. int sibCnt[10024];
  27. int p1, p2, points, lines,res;
  28.  
  29. void dfs (int node, bool first) {
  30. 	if (visited[node]) return;
  31. 	if (first && sibCnt[node]==1) res++;
  32. 	bool found = false;
  33. 	visited[node] = true;
  34. 	//DEBUG(sibCnt[node]);
  35. 	for (int i = 0; i < sibCnt[node]; i++)	{
  36. 		if (!visited[sib[node][i]]) {
  37. 			//cout << "Node " << sib[node][i] << endl;
  38. 			dfs (sib[node][i],false);
  39. 			found = true;
  40. 		}
  41. 	}
  42. 	if (!found) res++;
  43.  
  44. }
  45.  
  46. int main() {
  47.  
  48. 	while(scanf("%d%d",&points,&lines) == 2) {
  49. 		res = 0;
  50. 		bunny=false;
  51. 		REP(i,points+10) {
  52. 			visited[i]=false;
  53. 			sibCnt[i] = 0;
  54. 		}
  55. 		REP(i,lines) {
  56. 			scanf("%d%d",&p1,&p2);
  57. 			sib[p1][sibCnt[p1]++] = p2;
  58. 			sib[p2][sibCnt[p2]++] = p1;
  59. 		}
  60. 		REP(i,points+10) {
  61. 			dfs(1,true);
  62. 			if (res >= 4) {
  63. 				bunny = true;
  64. 				break;
  65. 			}
  66. 		}
  67. 		//cout << res << endl;
  68. 		if (bunny) cout << "YES" << endl;
  69. 		else cout << "NO" << endl;
  70. 	}
  71. 	return 0;
  72. }
  73.  

Diff to submission s465

fn.cpp

--- c5.s465.cteam027.fn.cpp.0.fn.cpp
+++ c5.s1002.cteam027.fn.cpp.0.fn.cpp
@@ -20,17 +20,50 @@
 #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
 
+bool bunny;
+int grade[10024];
+bool visited [10024];
+int sib[10024][10024];
+int sibCnt[10024];
+int p1, p2, points, lines,res;
+
+void dfs (int node, bool first) {
+        if (visited[node]) return;
+        if (first && sibCnt[node]==1) res++;
+        bool found = false;
+        visited[node] = true;
+        //DEBUG(sibCnt[node]);
+        for (int i = 0; i < sibCnt[node]; i++)  {
+                if (!visited[sib[node][i]]) {
+                        //cout << "Node " << sib[node][i] << endl;
+                        dfs (sib[node][i],false);
+                        found = true;
+                }
+        }
+        if (!found) res++;
+        
+}
+
 int main() {
-        bool bunny;
-        int grade[10024];
-        int p1, p2, points, lines;
+        
         while(scanf("%d%d",&points,&lines) == 2) {
-                bunny = false;
-                REP(i,points+10) grade[i] = 0;
+                res = 0;
+                bunny=false;
+                REP(i,points+10) {
+                        visited[i]=false;
+                        sibCnt[i] = 0;
+                }
                 REP(i,lines) {
                         scanf("%d%d",&p1,&p2);
-                        grade[p1]++;
-                        grade[p2]++;
-                        if (grade[p1] >= 4 || grade[p2] >= 4) bunny = true;
+                        sib[p1][sibCnt[p1]++] = p2;
+                        sib[p2][sibCnt[p2]++] = p1;
+                }
+                REP(i,points+10) {
+                        dfs(1,true);
+                        if (res >= 4) {
+                                bunny = true;
+                                break;
+                        }
                 }
+                //cout << res << endl;
                 if (bunny) cout << "YES" << endl;
                 else cout << "NO" << endl;