Source code for submission s1067

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. queue<int> q;
  23.  
  24. bool bunny;
  25. int grade[10024];
  26. bool visited [10024];
  27. int sib[10024][10024];
  28. int sibCnt[10024];
  29. int p1, p2, points, lines,res;
  30. /*
  31. void dfs (int node, bool first) {
  32. 	int cnt = 0;
  33. 	if (visited[node]) return;
  34. 	if (first && sibCnt[node]==1) res++;
  35. 	bool found = false;
  36. 	visited[node] = true;
  37. 	//DEBUG(sibCnt[node]);
  38. 	for (int i = 0; i < sibCnt[node]; i++)	{
  39. 		if (!visited[sib[node][i]]) {
  40. 			if (first) cnt++;
  41. 			//cout << "Node " << sib[node][i] << endl;
  42. 			dfs (sib[node][i],false);
  43. 			found = true;
  44. 		}
  45. 	}
  46. 	if (first && cnt==1) res++;
  47. 	if (!found) res++;
  48.  
  49.  
  50. }
  51. */
  52.  
  53. void bfs (int node) {
  54. 	bool found = false;
  55. 	if (visited[node]) return;
  56. 	q.push(node);
  57. 	if (sibCnt[node] == 1) res++;
  58. 	while(!q.empty()) {
  59. 		found = false;
  60. 		node = q.front(); q.pop();
  61. 		visited[node] = true;
  62. 		REP(i, sibCnt[node]) {
  63. 			if (!visited[sib[node][i]]) {
  64. 				q.push(sib[node][i]);
  65. 				found = true;
  66. 			}
  67. 		}
  68. 		if (!found) res++;
  69. 	}
  70. 	//DEBUG(res);
  71. }
  72.  
  73. int main() {
  74.  
  75. 	while(scanf("%d%d",&points,&lines) == 2) {
  76. 		bunny=false;
  77. 		REP(i,points+10) {
  78. 			visited[i]=false;
  79. 			sibCnt[i] = 0;
  80. 		}
  81. 		REP(i,lines) {
  82. 			scanf("%d%d",&p1,&p2);
  83. 			sib[p1][sibCnt[p1]++] = p2;
  84. 			sib[p2][sibCnt[p2]++] = p1;
  85. 		}
  86. 		FOR(i,1,points) {
  87. 			res = 0;
  88. 			bfs(i);
  89. 			if (res >= 4) {
  90. 				bunny = true;
  91. 				break;
  92. 			}
  93. 		}
  94. 		//cout << endl;
  95. 		if (bunny) cout << "YES" << endl;
  96. 		else cout << "NO" << endl;
  97. 	}
  98. 	return 0;
  99. }
  100.  

Diff to submission s1002

fn.cpp

--- c5.s1002.cteam027.fn.cpp.0.fn.cpp
+++ c5.s1067.cteam027.fn.cpp.0.fn.cpp
@@ -20,4 +20,6 @@
 #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
 
+queue<int> q;
+
 bool bunny;
 int grade[10024];
@@ -26,6 +28,7 @@
 int sibCnt[10024];
 int p1, p2, points, lines,res;
-
+/*
 void dfs (int node, bool first) {
+        int cnt = 0;
         if (visited[node]) return;
         if (first && sibCnt[node]==1) res++;
@@ -35,4 +38,5 @@
         for (int i = 0; i < sibCnt[node]; i++)  {
                 if (!visited[sib[node][i]]) {
+                        if (first) cnt++;
                         //cout << "Node " << sib[node][i] << endl;
                         dfs (sib[node][i],false);
@@ -40,6 +44,29 @@
                 }
         }
+        if (first && cnt==1) res++;
         if (!found) res++;
         
+        
+}
+*/
+
+void bfs (int node) {
+        bool found = false;
+        if (visited[node]) return;
+        q.push(node);
+        if (sibCnt[node] == 1) res++;
+        while(!q.empty()) {
+                found = false;
+                node = q.front(); q.pop();
+                visited[node] = true;
+                REP(i, sibCnt[node]) {
+                        if (!visited[sib[node][i]]) {
+                                q.push(sib[node][i]);
+                                found = true;
+                        }
+                }
+                if (!found) res++;
+        }
+        //DEBUG(res);
 }
 
@@ -47,5 +74,4 @@
         
         while(scanf("%d%d",&points,&lines) == 2) {
-                res = 0;
                 bunny=false;
                 REP(i,points+10) {
@@ -58,6 +84,7 @@
                         sib[p2][sibCnt[p2]++] = p1;
                 }
-                REP(i,points+10) {
-                        dfs(1,true);
+                FOR(i,1,points) {
+                        res = 0;
+                        bfs(i);
                         if (res >= 4) {
                                 bunny = true;
@@ -65,5 +92,5 @@
                         }
                 }
-                //cout << res << endl;
+                //cout << endl;
                 if (bunny) cout << "YES" << endl;
                 else cout << "NO" << endl;