Submission #108713

#TimeUsernameProblemLanguageResultExecution timeMemory
108713ckodserNetwork (BOI15_net)C++14
100 / 100
1369 ms105848 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define ld long double #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll mod=1e9+7; const ll maxn=5e5+500; const ll inf=1e9+900; vector<ll> ger[maxn]; set<pii> st; vector<ll> barg; pii dfs(ll a,ll p=-1){ if(ger[a].size()==1){ barg.pb(a); return mp(a,-1); } vector<pii> vec2; vector<ll> vec1; for(auto v:ger[a]){ if(v!=p){ pii r=dfs(v,a); if(r.S==-1)vec1.pb(r.F); else vec2.pb(r); } } if(vec2.size()==1){ if(vec1.empty()){ return vec2.back(); }else{ pii e=vec2.back(); st.erase(e); ll v=vec1.back(); vec1.pop_back(); st.insert(mp(e.F,v)); pii las=mp(e.F,v); vec1.pb(e.S); for(ll i=0;i+1<vec1.size();i+=2){ st.insert(mp(vec1[i],vec1[i+1])); } if(vec1.size()%2==1){ return mp(vec1.back(),-1); } else{ return las; } } }else{ pii las; for(auto e:vec2){ st.erase(e); } for(ll i=0;i<vec2.size();i++){ pii e=mp(vec2[i].S,vec2[(i+1)%vec2.size()].F); las=e; st.insert(e); } for(ll i=0;i+1<vec1.size();i+=2){ st.insert(mp(vec1[i],vec1[i+1])); las=mp(vec1[i],vec1[i+1]); } if(vec1.size()%2==1){ return mp(vec1.back(),-1); } else{ return las; } } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n; cin>>n; for(ll i=1;i<n;i++){ ll v,u; cin>>v>>u; ger[u].pb(v); ger[v].pb(u); } ll rot; for(ll i=1;i<=n;i++){ if(ger[i].size()>1)rot=i; } pii r=dfs(rot); if(r.S==-1 && r.F!=-1){ ll v=r.F; for(auto u:barg){ if(v!=u){ st.insert(mp(u,v)); break; } } } cout<<st.size()<<endl; for(auto e:st){ cout<<e.F<<' '<<e.S<<endl; } }

Compilation message (stderr)

net.cpp: In function 'std::pair<long long int, long long int> dfs(long long int, long long int)':
net.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(ll i=0;i+1<vec1.size();i+=2){
                 ~~~^~~~~~~~~~~~
net.cpp:61:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vec2.size();i++){
             ~^~~~~~~~~~~~
net.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i+1<vec1.size();i+=2){
             ~~~^~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:92:18: warning: 'rot' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pii r=dfs(rot);
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...