Source code for submission s1104

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. grade[i] = 0;
  81. }
  82. REP(i,lines) {
  83. scanf("%d%d",&p1,&p2);
  84. sib[p1][sibCnt[p1]++] = p2;
  85. sib[p2][sibCnt[p2]++] = p1;
  86. grade[p1]++;
  87. grade[p2]++;
  88. }
  89. FOR(i,1,points) {
  90. FOR(j,1,points) visited[i]=false;
  91. res = 0;
  92. bfs(i);
  93. if (res >= 4 || grade[i] >= 4) {
  94. bunny = true;
  95. break;
  96. }
  97. }
  98. //cout << endl;
  99. if (bunny) cout << "YES" << endl;
  100. else cout << "NO" << endl;
  101. }
  102. return 0;
  103. }
  104.  

Diff to submission s1074

fn.cpp

--- c5.s1074.cteam027.fn.cpp.0.fn.cpp
+++ c5.s1104.cteam027.fn.cpp.0.fn.cpp
@@ -78,4 +78,5 @@
                         visited[i]=false;
                         sibCnt[i] = 0;
+                        grade[i] = 0;
                 }
                 REP(i,lines) {
@@ -83,4 +84,6 @@
                         sib[p1][sibCnt[p1]++] = p2;
                         sib[p2][sibCnt[p2]++] = p1;
+                        grade[p1]++;
+                        grade[p2]++;
                 }
                 FOR(i,1,points) {
@@ -88,5 +91,5 @@
                         res = 0;
                         bfs(i);
-                        if (res >= 4) {
+                        if (res >= 4 || grade[i] >= 4) {
                                 bunny = true;
                                 break;