제출 #656028

#제출 시각아이디문제언어결과실행 시간메모리
656028mosaevNetwork (BOI15_net)C++17
18 / 100
23 ms35796 KiB
#include <bits/stdc++.h> #include <set> #include <map> #include <unordered_map> using namespace std; #define ll long long #define N (ll)(5e5+5) #define NP (2097155ll) #define M ((ll)1e9+7) #define fi first #define se second ll n, ct, r; vector<ll> v[N]; vector<pair<ll, ll>> ans; set<pair<ll, ll>> st[N], tmp; void dfs(ll s, ll p) { ct++; if (v[s].size() == 1) { st[s].insert({ ct, s }); return; } for (auto x : v[s]) if (x != p) { dfs(x, s); if (st[x].size() > st[s].size()) swap(st[x], st[s]); for (auto y : st[x]) st[s].insert(y); st[x].clear(); } tmp.clear(); for (auto x : st[s]) tmp.insert({ -x.first, x.second }); while (st[s].size() > 2) { ans.push_back({ (*st[s].begin()).second, (*tmp.begin()).second }); st[s].erase({ -(*tmp.begin()).first, tmp.begin()->second }); tmp.erase(tmp.begin()); tmp.erase({ -st[s].begin()->first, st[s].begin()->second }); st[s].erase(st[s].begin()); } } int main() { #define int ll ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n; ll a, b; for (int i = 1; i < n; i++) cin >> a >> b, v[a].push_back(b), v[b].push_back(a); for (int i = 1; i <= n; i++) if (v[i].size() > 1) r = i; dfs(r, 0); if (st[r].size() == 2) { pair<ll, ll> c = *st[r].begin(); st[r].erase(st[r].begin()); ans.push_back({ c.second, st[r].begin()->second }); } else if (st[r].size() == 1) { if (v[st[r].begin()->second][0] != r) ans.push_back({ r, st[r].begin()->second }); else ans.push_back({ st[r].begin()->second, ans.back().second }); } cout << ans.size() << '\n'; for (auto x : ans) cout << x.first << ' ' << x.second << '\n'; }

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

net.cpp: In function 'void dfs(long long int, long long int)':
net.cpp:20:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   20 |   for (auto y : st[x]) st[s].insert(y); st[x].clear();
      |   ^~~
net.cpp:20:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   20 |   for (auto y : st[x]) st[s].insert(y); st[x].clear();
      |                                         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...