Source code for submission s864

Go to diff to previous submission

fn.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <sstream>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10. #include <vector>
  11. #include <cstring>
  12.  
  13. using namespace std;
  14.  
  15. #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
  16. #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
  17. #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
  18.  
  19. #define PB push_back
  20. #define MP make_pair
  21.  
  22. #define MM(co, cim) memset((co), (cim), sizeof((co)))
  23.  
  24. #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
  25.  
  26. int p[10005], mdeg, mn, cnt, d[10014];
  27. vector<int> g[10014];
  28. queue<int> q;
  29.  
  30. int main ()
  31. {
  32. int m,n,a,b;
  33. while(cin >> n >> m){
  34. FOR(i, 0, 10014) g[i].clear();
  35. mdeg = 0;
  36. MM(p,0);
  37. MM(d,-1);
  38. FOR(i,0,m){
  39. cin >> a >> b;
  40. p[a]++;
  41. p[b]++;
  42. g[a].PB(b);
  43. g[b].PB(a);
  44. if (p[a] > mdeg)
  45. {
  46. mdeg = p[a];
  47. mn = a;
  48. }
  49. if (p[b] > mdeg)
  50. {
  51. mdeg = p[b];
  52. mn = b;
  53. }
  54. }
  55. cnt = 0;
  56. q.push(mn);
  57. d[mn] = 0;
  58. while (!q.empty())
  59. {
  60. int x = q.front(); q.pop();
  61. int temp = 0;
  62. for (int i = 0; i < g[x].size(); i++) if (d[g[x][i]] == -1)
  63. {
  64. d[g[x][i]] = d[x] + 1;
  65. ++temp;
  66. q.push(g[x][i]);
  67. }
  68. if (!temp) ++cnt;
  69. }
  70. printf("%s\n", cnt >= 4 ? "YES" : "NO");
  71. }
  72.  
  73. return 0;
  74. }
  75.  

Diff to submission s539

fn.cpp

--- c5.s539.cteam011.fn.cpp.0.fn.cpp
+++ c5.s864.cteam011.fn.cpp.0.fn.cpp
@@ -24,5 +24,7 @@
 #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
 
-int p[10005];
+int p[10005], mdeg, mn, cnt, d[10014];
+vector<int> g[10014];
+queue<int> q;
 
 int main ()
@@ -30,23 +32,41 @@
   int m,n,a,b;
   while(cin >> n >> m){
+    FOR(i, 0, 10014) g[i].clear();
+    mdeg = 0;
                 MM(p,0);
+                MM(d,-1);
                 FOR(i,0,m){
                         cin >> a >> b;
-                        p[a-1] ++;
-                        p[b-1] ++;
-                        
-                
-                }
-                bool ok = false;
-                FOR(i,0,n)
-                        if(p[i] >= 4){
-                                ok = true;
-                                break;
+                        p[a]++;
+                        p[b]++;
+                        g[a].PB(b);
+                        g[b].PB(a);
+                        if (p[a] > mdeg)
+                        {
+                          mdeg = p[a];
+                          mn = a;
                         }
-                        
-                if(ok)
-                        cout << "YES" << endl;
-                else
-                        cout << "NO" << endl;
+                        if (p[b] > mdeg)
+                        {
+                          mdeg = p[b];
+                          mn = b;
+                        }
+                }
+                cnt = 0;
+                q.push(mn);
+                d[mn] = 0;
+                while (!q.empty())
+                {
+                  int x = q.front(); q.pop();
+                  int temp = 0;
+                  for (int i = 0; i < g[x].size(); i++) if (d[g[x][i]] == -1)
+                  {
+                    d[g[x][i]] = d[x] + 1;
+                    ++temp;
+                    q.push(g[x][i]);
+                  }
+                  if (!temp) ++cnt;
+                }
+                printf("%s\n", cnt >= 4 ? "YES" : "NO");
         }