제출 #343075

#제출 시각아이디문제언어결과실행 시간메모리
343075mjhmjh1104Village (BOI20_village)C++14
100 / 100
200 ms30180 KiB
#include <queue> #include <cstdio> #include <vector> #include <numeric> #include <algorithm> using namespace std; const int MAX = 100006; int n, maxDepth[MAX], depth[MAX], childs[MAX], sz[MAX]; vector<int> adj[MAX], c[MAX]; int nextShort[MAX], e[MAX], resShort; int nextLong[MAX]; long long resLong; bool visited[MAX]; vector<int> tmp[MAX]; int tok[MAX]; int dfs(int x, int prev = -1) { sz[x] = 1; for (auto &i: adj[x]) if (i != prev) { c[x].push_back(i); sz[x] += dfs(i, x); } return sz[x]; } int centroid(int x, int prev = -1) { for (auto &i: adj[x]) if (i != prev && sz[i] > n / 2) return centroid(i, x); return x; } void dfsShort(int x) { e[x] = x; vector<int> zero; for (auto &i: c[x]) { if (!childs[i]) zero.push_back(i), e[x] = i; else { dfsShort(i); if (childs[i]) childs[x]--; else zero.push_back(i), e[x] = i; } } if (!childs[x]) return; if (zero.empty()) return; nextShort[x] = zero[0]; for (int i = 0; i < (int)zero.size(); i++) { if (i != (int)zero.size() - 1) nextShort[zero[i]] = zero[i + 1]; else nextShort[zero[i]] = x; resShort += 2; } } void depthFrom(int x, int prev = -1) { maxDepth[x] = depth[x]; for (auto &i: adj[x]) if (i != prev && !visited[i]) { depth[i] = depth[x] + 1; depthFrom(i, x); maxDepth[x] = max(maxDepth[x], maxDepth[i]); } } pair<int, int> farthest(int x, int prev = -1) { for (auto &i: adj[x]) if (i != prev && !visited[i]) { if (maxDepth[i] == maxDepth[x]) { pair<int, int> t = farthest(i, x); return { t.first, t.second + 1 }; } } return { x, 0 }; } void fl(int x, int prev, vector<int> &f) { f.push_back(x); for (auto &i: adj[x]) if (i != prev) fl(i, x, f); } int main() { scanf("%d", &n); fill(nextShort, nextShort + n, -1); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; adj[u].push_back(v); adj[v].push_back(u); } dfs(0); int ct = centroid(0); for (int i = 0; i < n; i++) childs[i] = (int)c[i].size(); dfsShort(0); if (nextShort[0] == -1) { nextShort[0] = c[0][0]; nextShort[e[c[0][0]]] = 0; resShort += 2; } for (int i = 0; i < n; i++) c[i].clear(); dfs(ct); depth[ct] = 0; depthFrom(ct); vector<pair<int, int>> v; for (auto &i: adj[ct]) v.push_back({ sz[i], i }); sort(v.begin(), v.end()); swap(v.front(), v.back()); int remainSum = 0; for (int i = 1; i < (int)v.size(); i++) remainSum += v[i].first; queue<pair<int, int>> q; vector<pair<int, int>> u; for (auto &i: adj[ct]) if (i != v[0].second) u.push_back({ i, sz[i] }); vector<int> res; for (auto &i: u) q.push(i); while (!q.empty()) { auto t = q.front(); q.pop(); if (!t.second) continue; t.second--; res.push_back(t.first); q.push(t); } int k = 0; vector<int> r; while (remainSum > v[0].first) { r.push_back(res[k++]); remainSum--; } while (v[0].first) { r.push_back(v[0].second); v[0].first--; if (remainSum) r.push_back(res[k++]), remainSum--; } for (int i = 0; i < (int)v.size(); i++) fl(v[i].second, ct, tmp[v[i].second]); vector<int> fin; for (auto &i: r) { resLong += depth[tmp[i][tok[i]]] * 2; fin.push_back(tmp[i][tok[i]++]); } for (int i = 0; i < n - 2; i++) nextLong[fin[i]] = fin[i + 1]; nextLong[fin[n - 2]] = ct; nextLong[ct] = fin[0]; printf("%d %lld\n", resShort, resLong); for (int i = 0; i < n; i++) printf("%d ", nextShort[i] + 1); puts(""); for (int i = 0; i < n; i++) printf("%d ", nextLong[i] + 1); }

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

Village.cpp: In function 'int main()':
Village.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Village.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...