제출 #546663

#제출 시각아이디문제언어결과실행 시간메모리
546663OlympiaVillage (BOI20_village)C++17
100 / 100
220 ms33752 KiB
#include <cmath> #include <iostream> #include <set> #include <climits> #include <cstdio> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <iomanip> #include <unordered_map> #include <type_traits> #include <string> #include <queue> #include <map> #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") using namespace std; vector<vector<int>> adj; vector<int> ord; int t = 0; int c = 0; vector<int64_t> pre, post, depth, sub; vector<vector<int>> dp; bool isAncestor(int u, int v) { return (pre[u] <= pre[v] && post[u] >= post[v]); } int lca(int u, int v) { if (isAncestor(u, v)) return u; if (isAncestor(v, u)) return v; for (int i = 19; i >= 0; i--) if (!isAncestor(dp[u][i], v))u = dp[u][i]; return dp[u][0]; } void find_sub(int curNode, int prevNode) { sub[curNode] = 1; for (int i: adj[curNode]) if (i != prevNode) find_sub(i, curNode), sub[curNode] += sub[i]; } int get_centroid(int curNode, int prevNode) { for (int i: adj[curNode]) { if (i == prevNode) continue; if (sub[i] > (int) adj.size() / 2) return get_centroid(i, curNode); } return curNode; } void f(int curNode, int prevNode) { depth[curNode] = depth[prevNode] + 1; dp[curNode].resize(20); dp[curNode][0] = prevNode; for (int i = 1; i < 20; i++)dp[curNode][i] = dp[dp[curNode][i - 1]][i - 1]; ord[curNode] = t++, pre[curNode] = c++; for (int i:adj[curNode]) if (i != prevNode)f(i, curNode); post[curNode] = c++; } vector<int> ans; int tot = 0; void dfs (int curNode, int prevNode) { for (int i: adj[curNode]) { if (i == prevNode) continue; dfs(i, curNode); if (ans[curNode] == -1 && ans[i] == -1) ans[curNode] = i, ans[i] = curNode, tot++; else if (ans[i] == -1) ans[i] = ans[curNode], ans[curNode] = i, tot++; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; adj.resize(n), depth.assign(n, false), dp.resize(n), pre.resize(n), post.resize(n), sub.resize(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--, adj[u].push_back(v), adj[v].push_back(u); } find_sub(0, -1); ord.resize(n), ans.assign(n, -1); int centroid = get_centroid(0, -1); f(centroid, centroid); dfs(0, -1); if (ans[0] == -1) ans[0] = ans[adj[0].back()], ans[adj[0].back()] = 0, tot++; int64_t al = 0; map<int, int> myMap; for (int i = 0; i < ord.size(); i++) myMap[ord[i]] = i; vector<int> ansr(n); for (int i = 0; i < n; i++) ansr[myMap[i]] = myMap[(i + n / 2 + n) % n]; for (int i = 0; i < n; i++) al += depth[i] + depth[ansr[i]] - 2 * depth[lca(i, ansr[i])]; cout << tot * 2 << " " << al << '\n'; for (int i = 0; i < n; i++) cout << ans[i] + 1 << ' '; cout << '\n'; for (int i: ansr) cout << i + 1 << ' '; }

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

Village.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("O3")
      | 
Village.cpp:19: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   19 | #pragma GCC optimization ("unroll-loops")
      | 
Village.cpp: In function 'int main()':
Village.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < ord.size(); i++) myMap[ord[i]] = i;
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...