Source code for submission s858

Go to diff to previous submission

fn.cpp

  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <algorithm>
  6. #include <numeric>
  7. #include <utility>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <string>
  15. #include <queue>
  16.  
  17. #define vi vector <int>
  18. #define vl vector <long long>
  19. #define vpii vector <pair <int,int> >
  20. #define mp(x,y) make_pair(x,y)
  21. #define all(x) (x).begin(),(x).end()
  22. #define sz(x) (int)(x).size()
  23. #define FOR(i,n) for(ll i=0;i<int(n);i++)
  24. #define READ(v,n) {FOR(i,n){ll x;cin>>x;v.pb(x);} }
  25. #define gmin(a,b) {if (b<a) a=b;}
  26. #define gmax(a,b) {if (b>a) a=b;}
  27. #define pb push_back
  28. #define ppb pop_back
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. using namespace std;
  32.  
  33. int main(){
  34. int n, m;
  35. while(cin>>n>>m){
  36. vi v;
  37. vector <vi> edges(n,v);
  38. vi es(n,0);
  39. FOR(i,m){
  40. int x,y;
  41. cin>>x>>y;
  42. edges[x-1].pb(y-1);
  43. edges[y-1].pb(x-1);
  44. es[x-1]++;
  45. es[y-1]++;
  46. }
  47. FOR(i,n){
  48. vi used(n,0);
  49. vpii q;
  50. // priority_queue <int> q;
  51. vi edgesize=es;
  52.  
  53. q.pb(mp(i,n-sz(edges[i])));
  54.  
  55. FOR(j,edges[i].size()){edgesize[edges[i][j]]--;}
  56. used[i]=1;
  57. while(q.size()!=0){
  58. if(q.size()>=4){cout<<"YES"<<endl;goto end;}
  59. pair <int,int> y=q[q.size()-1];
  60. q.ppb();
  61. int x=y.first;
  62. FOR(j,edges[x].size()){
  63. int next=edges[x][j];
  64. if(used[next]==0){
  65. edgesize[next]--;
  66. FOR(k,sz(edges[next])){
  67. edgesize[edges[next][k]]--;
  68. }
  69. q.pb(mp(next,edgesize[next]));
  70. int w=0;
  71. while(w<sz(q) && q[w].second<edgesize[next]) w++;
  72. q.insert(q.begin()+w,mp(next,edgesize[next]));
  73. used[next]=1;
  74. }
  75. }
  76. }
  77. }
  78. cout<<"NO"<<endl;
  79. end:
  80. }
  81.  
  82. return 0;
  83. }
  84.  
  85.  
  86.  

Diff to submission s664

fn.cpp

--- c5.s664.cteam012.fn.cpp.0.fn.cpp
+++ c5.s858.cteam012.fn.cpp.0.fn.cpp
@@ -77,8 +77,7 @@
     }
     cout<<"NO"<<endl;
-
+    end:
   }
   
-  end:
   return 0;
 }