제출 #902741

#제출 시각아이디문제언어결과실행 시간메모리
902741aqxaNetwork (BOI15_net)C++17
63 / 100
728 ms127952 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long // works? struct graph { vector<vector<int>> adj; int n; graph() {} graph(int _n) : n(_n) { adj.resize(n); } inline void add(int x, int y) { adj[x].push_back(y); adj[y].push_back(x); } }; struct lca_graph : graph { using graph::adj; using graph::n; vector<vector<int>> par; vector<int> lev, path; int lv = 0, lg; lca_graph(int _n) : graph(_n) { lg = __lg(n) + 1; par = vector<vector<int>>(n, vector<int>(lg, -1)); lev = vector<int>(n, 0); } void make_lca(int x, int p) { path.push_back(x); lv++; lev[x] = lv; for (int i = 0; (1<<i) < path.size(); ++i) { par[x][i] = path[path.size()-1-(1<<i)]; } for (auto u: adj[x]) { if (u != p) { make_lca(u, x); } } lv--; path.pop_back(); } int ka(int u, int k) { if (k > lev[u] - 1) return 0; while (k > 0) { int clg = (int) __lg(k); k -= (1 << clg); u = par[u][clg]; } return u; } int lca(int u, int v) { int du = lev[u], dv = lev[v]; if (du < dv) { v = ka(v, dv - du); dv = du; } else if (du > dv) { u = ka(u, du - dv); du = dv; } if (u == v) return u; for (int i = lg-1; i >= 0; --i) { if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; assert(u != -1 && v != -1); } } assert(u != -1); return par[u][0]; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); // int tt; // cin >> tt; // while (tt--) { int n; cin >> n; lca_graph g(n); for (int i = 0; i < n - 1; ++i) { int x, y; cin >> x >> y; g.add(--x, --y); } vector<int> leafs; set<int> leaf; for (int i = 0; i < n; ++i) { if ((int) g.adj[i].size() == 1) { leaf.insert(i); leafs.push_back(i); } } for (int i = 0; i < n; ++i) { if (leaf.find(i) == leaf.end()) { g.make_lca(i, -1); break; } } if ((int) leafs.size() % 2) { int x = leafs.back(); for (int i = 0; i < n; ++i) { if (i != x && i != g.adj[x][0] && leaf.find(i) == leaf.end()) { leafs.push_back(i); break; } } } vector<pair<int, int>> ans; for (int i = 0; i + 1 < (int) leafs.size(); i += 2) { if (!ans.size()) { ans.push_back(make_pair(leafs[i], leafs[i + 1])); continue; } auto p = ans.back(); ans.pop_back(); vector<int> v = {p.first, p.second, leafs[i], leafs[i + 1]}; int best = 0; pair<int, int> c = {2 * n, 2 * n}; for (int f = 1; f < 4; ++f) { int a = g.lca(v[0], v[f]), b; for (int j = 1; j < 4; ++j) { for (int k = j + 1; k < 4; ++k) { if (j != f && k != f) { b = g.lca(v[j], v[k]); // cout << "Good\n"; } } } a = g.lev[a]; b = g.lev[b]; if (a > b) swap(a, b); pair<int, int> cur = {a, b}; if (cur < c) { best = f; c = cur; } } ans.push_back({v[0], v[best]}); for (int j = 1; j < 4; ++j) { for (int k = j + 1; k < 4; ++k) { if (j != best && k != best) { ans.push_back({v[j], v[k]}); } } } } cout << (int) ans.size() << "\n"; for (auto [x, y]: ans) { cout << x + 1 << " " << y + 1 << "\n"; } // } return 0; }

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

net.cpp: In member function 'void lca_graph::make_lca(int, int)':
net.cpp:37:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 0; (1<<i) < path.size(); ++i) {
      |                         ~~~~~~~^~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:145:15: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |    b = g.lev[b];
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...