제출 #933686

#제출 시각아이디문제언어결과실행 시간메모리
933686oblantisNetwork (BOI15_net)C++17
0 / 100
5 ms12172 KiB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector using namespace std; typedef long long ll; typedef pair<int, int> pii; const int inf = 1e9; const int mod = 1e9+7; const int maxn = 5e5 + 1; vt<pii> ans; vt<int> g[maxn]; pii dfs(int v, int p){ int pr = -1, rp = -1; if(g[v].size() == 1)pr = v; for(auto i : g[v]){ if(i == p)continue; pii wt = dfs(i, v); if(pr == -1)pr = wt.ff; else if(wt.ff != -1){ if(rp == -1)rp = wt.ff; else { ans.pb({rp, wt.ff}); rp = -1; } } if(wt.ss != -1){ if(rp == -1)rp = wt.ss; else { ans.pb({rp, wt.ss}); rp = -1; } } } return {pr, rp}; } void solve() { int n; cin >> n; for(int i = 0, u, v; i < n - 1; i++){ cin >> u >> v; g[u].pb(v), g[v].pb(u); } int t = 1; for(int i = 1; i <= n; i++)if((int)g[i].size() > 1)t = i; pii wt = dfs(t, 0); if(wt.ss != -1)ans.pb({wt.ff, wt.ss}); else ans.pb({wt.ff, wt.ff % n + 1}); cout << ans.size() << '\n'; for(auto i : ans)cout << i.ff << ' ' << i.ss << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int times = 1; //cin >> times; for(int i = 1; i <= times; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...