Submission #286608

#TimeUsernameProblemLanguageResultExecution timeMemory
286608MarlovNetwork (BOI15_net)C++14
0 / 100
155 ms262148 KiB
/* Code by @marlov */ #include <iostream> #include <fstream> #include <string> #include <sstream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <iomanip> #include <utility> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <stack> #include <queue> #include <iterator> using namespace std; typedef long long ll; typedef pair<int,int> pi; #define maxN 500000 int N; int tl=0; int leaves[maxN]; int root=0; vector<int> adj[maxN]; vector< pair<int,int> > edges; queue<int> vals[maxN]; void findRoot(int n,int p){ if(adj[n].size()==1){ leaves[n]++; } bool wks=true; for(int i:adj[n]) if(i!=p){ findRoot(i,n); if(leaves[i]>floor(tl/2)) wks=false; leaves[n]+=leaves[i]; } if(tl-leaves[n]>floor(tl/2)) wks=false; if(wks&&adj[n].size()>1) root=n; } void dfs(int n,int p){ if(adj[n].size()==1){ vals[n].push(n); return; } int lv=n; for(int i:adj[n]) if(i!=p){ dfs(i,n); if(vals[i].size()>vals[lv].size()) lv=i; } //swap(vals[n],vals[lv]); for(int i:adj[n]) if(i!=p){ while(vals[n].size()>(n==root?0:1)&&vals[i].size()>0){ edges.push_back(make_pair(vals[n].front(),vals[i].front())); vals[n].pop(); vals[i].pop(); } while(vals[i].size()>0){ vals[n].push(vals[i].front()); vals[i].pop(); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>N; int u,v; for(int i=0;i<N-1;i++){ cin>>u>>v; u--;v--; adj[u].push_back(v); adj[v].push_back(u); } for(int i=0;i<N;i++){ if(adj[i].size()==1) tl++; } //cout<<root<<endl; findRoot(0,-1); cout<<root<<'\n'; dfs(root,-1); while(vals[root].size()>1){ int f=vals[root].front();vals[root].pop(); int s=vals[root].front();vals[root].pop(); edges.push_back(make_pair(f,s)); } if(vals[root].size()==1){ edges.push_back(make_pair(vals[root].front(),root)); } cout<<edges.size()<<'\n'; for(int i=0;i<(int)edges.size();i++){ cout<<edges[i].first+1<<" "<<edges[i].second+1<<'\n'; } return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1,n=0?) * do smth instead of nothing and stay organized */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...