Submission #1008712

#TimeUsernameProblemLanguageResultExecution timeMemory
1008712ByeWorldNetwork (BOI15_net)C++14
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") #define ll long long #define int long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii, int> ipii; const int MAXN = 3e3+10; const int INF = 1e18+10; const int LOG = 19; const int MOD = 1e9+7; const int SQRT = 450; const vector<int> NOL = {}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; int n; vector <int> adj[MAXN]; vector <pii> ans; set <pii> s; int root, cnt, deg[MAXN]; vector <int> leaf[MAXN]; void dfs(int nw, int par){ if(adj[nw].size()==1) leaf[cnt].pb(nw); for(auto nx : adj[nw]){ if(nx==par) continue; dfs(nx, nw); } } signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; for(int i=1; i<=n-1; i++){ int x, y; cin >> x >> y; adj[x].pb(y); adj[y].pb(x); } int LE = 0; for(int i=1; i<=n; i++){ if(adj[i].size()!=1) root = i; else LE++; } for(auto nx : adj[root]){ ++cnt; dfs(nx, root); } for(int i=1; i<=cnt; i++){ deg[i] = leaf[i].size(); s.insert({leaf[i].size(), i}); } int las = 1; // cout << root << "\n"; while(ans.size() != LE/2){ int fr = (*(s.begin())).se, en = (*(--s.end())).se; // cout << fr << ' ' << en << " fr\n"; s.erase(s.begin()); if(fr != en) s.erase(--s.end()); int l = leaf[fr].back(); leaf[fr].pop_back(); deg[fr]--; int r = leaf[en].back(); leaf[en].pop_back(); deg[en]--; las = r; ans.pb({l, r}); if(deg[fr] != 0) s.insert({deg[fr], fr}); if(fr != en) if(deg[en] != 0) s.insert({deg[en], en}); } if(LE%2){ int l = leaf[(*(s.begin())).se].back(); ans.pb({l, las}); } cout << ans.size() << '\n'; for(auto in : ans) cout << in.fi << ' ' << in.se << '\n'; }

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |  while(ans.size() != LE/2){
      |        ~~~~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...