Source code for submission s753

Go to diff to previous submission

fn.cpp

  1. #include<iostream>
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<ctype.h>
  6. #include<math.h>
  7.  
  8. #include<vector>
  9. #include<set>
  10.  
  11. using namespace std;
  12.  
  13. #define FOR(i,a,b) for(int i=a; i<=b; i++)
  14.  
  15. #define PII pair<int, int>
  16. #define MP make_pair
  17. #define PB push_back
  18.  
  19. #define SIZE(s) ((int)(s).size())
  20.  
  21. #define ll long long
  22.  
  23. #define MAX 10047
  24.  
  25. int N, M;
  26. vector<int> G[MAX];
  27.  
  28. int colors[MAX];
  29. int color;
  30.  
  31. void dfs(int v)
  32. {
  33. colors[v] = color;
  34. FOR(i,0, SIZE(G[v])-1)
  35. {
  36. int u = G[v][i];
  37. if (colors[u] == 0)
  38. dfs(u);
  39. }
  40. }
  41.  
  42. int V[MAX];
  43.  
  44. int st4[MAX];
  45. vector<int> st3[MAX];
  46.  
  47. //skusime medzi dvoma vrcholmi
  48. bool skus(int v1, int v2)
  49. {
  50. // cout << v1 << " " << v2 << endl;
  51. set<int> vrchols;
  52. FOR(i,0, SIZE(G[v1])-1) if (G[v1][i] != v2) vrchols.insert( G[v1][i] );
  53. FOR(i,0, SIZE(G[v2])-1) if (G[v2][i] != v1) vrchols.insert( G[v2][i] );
  54. return SIZE(vrchols) >= 4;
  55. }
  56.  
  57. int main()
  58. {
  59. int a, b;
  60. while(scanf("%d %d",&N, &M)== 2)
  61. {
  62. FOR(i,0,N-1) G[i].clear();
  63. FOR(i,0,N-1) V[i] = 0;
  64. while(M--)
  65. {
  66. scanf("%d %d",&a,&b);
  67. a--; b--;
  68. G[a].PB(b);
  69. G[b].PB(a);
  70. V[a]++;
  71. V[b]++;
  72. }
  73.  
  74. color = 0;
  75. FOR(i,0,N-1) colors[i] = 0;
  76. FOR(i,0,N-1)
  77. {
  78. if (colors[i] == 0)
  79. {
  80. color++;
  81. dfs(i);
  82. }
  83. }
  84.  
  85. // FOR(i,0,N-1) cout << colors[i] << endl;
  86.  
  87. bool ok = false;
  88. FOR(c,1,color)
  89. {
  90. st4[c] = 0;
  91. st3[c].clear();
  92. }
  93. FOR(i,0,N-1)
  94. {
  95. if (V[i] > 3)
  96. st4[ colors[i] ]++;
  97. if (V[i] > 2)
  98. st3[ colors[i] ].PB(i);
  99. }
  100.  
  101. FOR(c,1,color)
  102. {
  103. if (st4[c] >= 1)
  104. {
  105. ok = true;
  106. break;
  107. }
  108. if (SIZE(st3[c]) > 1)
  109. {
  110. FOR(i,0, SIZE( st3[c])-1)
  111. FOR(j, i+1 , SIZE(st3[c])-1)
  112. {
  113. if (skus( st3[c][i], st3[c][j]))
  114. {
  115. ok = true;
  116. break;
  117. }
  118. }
  119. }
  120. }
  121.  
  122. if (ok) puts("YES");
  123. else puts("NO");
  124. }
  125. return 0;
  126. }
  127.  
  128.  

Diff to submission s748

fn.cpp

--- c5.s748.cteam079.fn.cpp.0.fn.cpp
+++ c5.s753.cteam079.fn.cpp.0.fn.cpp
@@ -111,6 +111,9 @@
                                         FOR(j, i+1 , SIZE(st3[c])-1)
                                         {
-                                                if (skus( st3[c][i], st3[c][j])) ok = true;
-                                                break;
+                                                if (skus( st3[c][i], st3[c][j])) 
+                                                {
+                                                        ok = true;
+                                                        break;
+                                                }
                                         }
                         }