Submission #396500

#TimeUsernameProblemLanguageResultExecution timeMemory
396500Kevin_Zhang_TW즐거운 행로 (APIO20_fun)C++17
21 / 100
1077 ms39076 KiB
#include <bits/stdc++.h> #include "fun.h" using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 100010, MAX_D = 17; int qdis(int a, int b) { return hoursRequired(a, b); } int sbsz(int rt, int x) { return attractionsBehind(rt, x); } // always go to the farthest point possible // but it doesn't rely on deg(x) <= 3 int dep[MAX_N], in[MAX_N], out[MAX_N], anc[MAX_D][MAX_N]; vector<int> edge[MAX_N]; bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; } int get_lca(int a, int b) { if (isanc(a, b)) return a; if (isanc(b, a)) return b; for (int i = MAX_D-1;i >= 0;--i) if (!isanc(anc[i][a], b)) a = anc[i][a]; return anc[0][a]; } int dis(int a, int b) { return dep[a] + dep[b] - 2 * dep[get_lca(a, b)]; } void dfs_init(int x, int lst) { static int t; anc[0][x] = lst; for (int d = 1;d < MAX_D;++d) anc[d][x] = anc[d-1][ anc[d-1][x] ]; in[x] = t++; for (int u : edge[x]) if (u != lst) { dep[u] = dep[x] + 1; dfs_init(u, x); } out[x] = t; } struct node { vector<int> cand; node () {} node (vector<int> c) : cand(c) {} node (node a, node b) { cand = a.cand; for (int u : b.cand) { if (cand.size() <= 1) { cand.pb(u); continue; } int &x = cand[0], &y = cand[1]; int da = dis(u, x), db = dis(u, y); if (da < db) swap(da, db), swap(x, y); if (da <= dis(x, y)) continue; y = u; } }; }; struct sgt { int n; vector<node> val; sgt(int n) : n(n) { val.resize(n<<1); for (int i = 0;i < n;++i) val[i+n] = node({i}); for (int i = n-1;i > 0;--i) val[i] = node(val[i<<1], val[i<<1|1]); } void kill(int i) { val[i+n] = node(); for (i += n;i>>=1;) { val[i] = node(val[i<<1], val[i<<1|1]); } } vector<int> qry() { return val[1].cand; } }; vector<int> gen_ans(int N, vector<pair<int,int>> alle) { for (auto [a, b] : alle) { edge[a].pb(b), edge[b].pb(a); } dfs_init(0, 0); sgt tree(N); int x = tree.qry()[0]; vector<int> res {x}; tree.kill(x); for (int i = 1;i < N;++i) { auto vec = tree.qry(); int a = vec[0], b = end(vec)[-1]; if (dis(x, b) > dis(x, a)) swap(a, b); res.pb(x = a); tree.kill(x); } return res; } std::vector<int> createFunTour(int N, int Q) { vector<pair<int,int>> alle; for (int i = 1;i < N;++i) alle.pb(i, (i-1)/2); // for (int i = 0;i < N;++i) // for (int j = i+1;j < N;++j) // if (qdis(i, j) == 1) // alle.pb(i, j); return gen_ans(N, alle); // vector<int> ans; // // vector<int> vis(N); // // assert(1ll * N * N <= Q); // // auto getfar = [&](int x) { // int p = -1, d = -1; // for (int i = 0;i < N;++i) // if (x != i && !vis[i]) { // if (chmax(d, qdis(x, i))) // p = i; // } // return p; // }; // // ans.pb(getfar(0)); // // for (int i = 1;i < N;++i) { // vis[ans[i-1]] = true; // ans.pb(getfar(ans[i-1])); // } // // return ans; }
#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...