제출 #107920

#제출 시각아이디문제언어결과실행 시간메모리
107920shash42Network (BOI15_net)C++11
18 / 100
2037 ms24056 KiB
#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define pii pair<int, int> using namespace std; const int N=5e5+5; int n, tmr=0; vector<int> adj[N], lvlst[N]; vector< pii > ans; int lv[N], p[N]; struct lvsrt { bool operator()(const int &a, const int &b) { return lv[a]>lv[b]; } }; void dfs(int u) { for(auto &v: adj[u]) { if(v!=p[u]) { p[v]=u; dfs(v); lv[u]+=lv[v]; } } if(adj[u].size()==1 && u!=1) { tmr++; lv[u]=1; } } int findg(int u) { //cout << tmr << " finding g: " << u << endl; for(auto &v: adj[u]) { if(lv[v]>tmr/2 && p[u]!=v) { return findg(v); } } return u; } void findlvs(int u, int subt) { for(auto &v: adj[u]) { if(v!=p[u]) { p[v]=u; findlvs(v, subt); } } if(adj[u].size()==1) { lvlst[subt].pb(u); } } int main() { cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } p[1]=1; dfs(1); if(adj[1].size()==1) tmr++; int g=findg(1); // cout << g; sort(adj[g].begin(), adj[g].end(), lvsrt()); memset(p, 0, n+1); int numsubt=adj[g].size(); for(int i = 0; i < numsubt; i++) { p[adj[g][i]]=g; findlvs(adj[g][i], i); } int itr; for(int i = 0; i < numsubt; i++) { itr=i+1; while(lvlst[i].size()) { if(ans.size()==tmr/2) break; while(!lvlst[itr].size()) { itr++; if(itr==numsubt) itr=i+1; } if(itr>=numsubt) break; ans.pb(mp(lvlst[i].back(), lvlst[itr].back())); lvlst[i].pop_back(); lvlst[itr].pop_back(); itr++; if(itr==numsubt) itr=i+1; } } if(tmr%2) { for(int i = 0; i < numsubt; i++) { if(lvlst[i].size()) ans.pb(mp(lvlst[i][0], g)); } } cout << ans.size() << "\n"; for(auto &v: ans) { cout << v.first << " " << v.second << "\n"; } }

컴파일 시 표준 에러 (stderr) 메시지

net.cpp: In function 'int main()':
net.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ans.size()==tmr/2) break;
       ~~~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...