Submission #1262140

#TimeUsernameProblemLanguageResultExecution timeMemory
1262140cpismylifeOwOFun Tour (APIO20_fun)C++20
0 / 100
77 ms15292 KiB
#include <bits/stdc++.h> #ifndef cpismylifeOwO #include "fun.h" #endif // cpismylifeOwO using namespace std; const long long mod = 1e9 + 7; const int MaxN = 1e6 + 5; const int MaxLog = 20; #ifdef cpismylifeOwO int ni; vector<int> graph[MaxN]; void Inp() { cin >> ni; for (int x = 1; x < ni; x++) { int u, v; cin >> u >> v; u++; v++; graph[u].push_back(v); graph[v].push_back(u); } } int par[MaxN]; int h[MaxN]; int sz[MaxN]; void PreDFS(int u, int p) { sz[u] = 1; for (int x : graph[u]) { if (x != p) { par[x] = u; h[x] = h[u] + 1; PreDFS(x, u); sz[u] += sz[x]; } } } int BinLift[MaxLog][MaxN]; void Build() { for (int x = 1; x <= ni; x++) { BinLift[0][x] = par[x]; } for (int x = 1; x < MaxLog; x++) { for (int y = 1; y <= ni; y++) { BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]]; } } } int LCA(int u, int v) { if (h[u] != h[v]) { if (h[u] > h[v]) { swap(u, v); } int k = h[v] - h[u]; for (int x = 0; x < MaxLog; x++) { if (k & (1 << x)) { v = BinLift[x][v]; } } } if (u == v) { return v; } for (int x = MaxLog - 1; x >= 0; x--) { if (BinLift[x][u] != BinLift[x][v]) { u = BinLift[x][u]; v = BinLift[x][v]; } } return par[u]; } int hoursRequired(int u, int v) { cout << "a "; u++; v++; cout << u << " " << v << " "; int lca = LCA(u, v); cout << h[u] + h[v] - 2 * h[lca] << "\n"; return h[u] + h[v] - 2 * h[lca]; } int attractionsBehind(int u, int v) { cout << "b "; u++; v++; cout << u << " " << v << " "; int lca = LCA(u, v); if (lca == v) { for (int x = MaxLog - 1; x >= 0; x--) { if (h[u] - (1 << x) > h[v]) { u = BinLift[x][u]; } } cout << ni - sz[u] << "\n"; return ni - sz[u]; } cout << sz[v] << "\n"; return sz[v]; } #endif // cpismylifeOwO int dis[MaxN]; priority_queue<pair<int, int>> group[5]; vector<int> createFunTour(int n, int Q) { assert(Q >= 0); pair<int, int> cur = make_pair(n, 1); for (int x = 2; x <= n; x++) { int p = attractionsBehind(0, x - 1); if (p > n / 2) { cur = min(cur, make_pair(p, x)); } } int r = cur.second; vector<int> af; for (int x = 1; x <= n; x++) { if (x != r) { dis[x] = hoursRequired(r - 1, x - 1); } if (dis[x] == 1) { af.push_back(x); } } for (int x = 1; x <= n; x++) { if (x != r) { bool done = false; for (int y = 0; y < (int)af.size() - 1; y++) { int v = af[y]; if (hoursRequired(v - 1, x - 1) + 1 == dis[x]) { group[y].push(make_pair(dis[x], x)); done = true; } } if (!done) { group[(int)af.size() - 1].push(make_pair(dis[x], x)); } } } vector<int> res; int curm = -1; if ((int)af.size() == 3) { while (2 * max(group[0].size(), max(group[1].size(), group[2].size())) != group[0].size() + group[1].size() + group[2].size()) { pair<pair<int, int>, int> now = make_pair(make_pair(0, 0), 0); for (int x = 0; x < 3; x++) { if (curm != x && !group[x].empty()) { now = max(now, make_pair(group[x].top(), x)); } } curm = now.second; group[now.second].pop(); res.push_back(now.first.second - 1); } if (group[1].size() > group[0].size()) { swap(group[0], group[1]); if (curm == 0 || curm == 1) { curm ^= 1; } } if (group[2].size() > group[0].size()) { swap(group[2], group[0]); if (curm == 0 || curm == 2) { curm ^= 2; } } while (!group[2].empty()) { group[1].push(group[2].top()); group[2].pop(); } if (curm == 2) { curm = 1; } } while (!group[0].empty() || !group[1].empty()) { pair<pair<int, int>, int> now = make_pair(make_pair(0, 0), 0); for (int x = 0; x < 2; x++) { if (curm != x && !group[x].empty()) { now = max(now, make_pair(group[x].top(), x)); } } curm = now.second; group[now.second].pop(); res.push_back(now.first.second - 1); } res.push_back(r - 1); return res; } #ifdef cpismylifeOwO void Exc() { PreDFS(1, -1); Build(); vector<int> res = createFunTour(ni, 4e5); for (int x : res) { cout << x << " "; } } int main() { freopen("FUN.INP", "r", stdin); //freopen("FUN.OUT", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); int test = 1; //cin >> test; for (int x = 1; x <= test; x++) { Inp(); Exc(); } return 0; } #endif // cpismylifeOwO
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...