제출 #502966

#제출 시각아이디문제언어결과실행 시간메모리
502966Victor즐거운 행로 (APIO20_fun)C++17
0 / 100
1 ms300 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include "fun.h" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; int n, q, sub_size[100001], dist[100001]; vii subtrees[3]; std::vector<int> createFunTour(int N, int Q) { if (N == 2) { vi vec = {0, 1}; return vec; } n = N; q = Q; int centroid = 0, mn = INF; rep(i, 1, n) { sub_size[i] = attractionsBehind(0, i); if (sub_size[i] >= (n + 1) / 2 && sub_size[i] < mn) { centroid = i; mn = sub_size[i]; } } int cnt = 0; vi neighbours; rep(i, 0, n) if (i != centroid) { dist[i] = hoursRequired(centroid, i); if (dist[i] == 1) { neighbours.pb(i); ++cnt; } } rep(i, 0, n) if (i != centroid) { per(j, 0, cnt) { bool yes = !j; if (j) yes = hoursRequired(centroid, i) == hoursRequired(neighbours[j], i) + 1; if (yes) { subtrees[j].emplace_back(dist[i], i); break; } } } vi ans; rep(i, 0, cnt) sort(all(subtrees[i])); int prev = -1; if (cnt == 3) { while (1) { vii sizes; rep(i, 0, cnt) sizes.emplace_back(sz(subtrees[i]), i); sort(all(sizes)); if (sizes[0].first + sizes[1].first == sizes[2].first) { int smallest = sizes[0].second, small = sizes[1].second; if (smallest < small) swap(small, smallest); trav(val, subtrees[smallest]) subtrees[small].pb(val); if (!small) subtrees[0].swap(subtrees[1]); if (prev == small || prev == smallest) prev = 1; else prev = 0; break; } int node, sub, val = -1; rep(i, 0, cnt) if (prev!=i&&subtrees[i].back().first > val) { tie(val, node) = subtrees[i].back(); sub = i; } subtrees[sub].pop_back(); ans.pb(node); prev = sub; } } rep(i, 0, cnt) sort(all(subtrees[i])); if (prev == -1) prev = sz(subtrees[0]) > sz(subtrees[1]); while (1) { prev^=1; if(subtrees[prev].empty())break; ans.pb(subtrees[prev].back().second); subtrees[prev].pop_back(); } ans.pb(centroid); //trav(val,ans)cout<<"u = "<<val<<endl; return ans; } /* static void wrongAnswer(std::string message) { printf("WA: %s\n", message.c_str()); exit(0); } namespace tree_helper { static int N; static int logN; static std::vector<std::vector<int>> parent; static std::vector<int> depth; static std::vector<int> subtree_size; static void dfs( const std::vector<std::vector<int>>& adj_list, int current_node, int parent_node) { parent[0][current_node] = parent_node; subtree_size[current_node] = 1; for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) { const int next_node = adj_list[current_node][i]; if (next_node != parent_node) { depth[next_node] = depth[current_node] + 1; dfs(adj_list, next_node, current_node); subtree_size[current_node] += subtree_size[next_node]; } } } static void initializeTree(const std::vector<std::vector<int>>& adj_list) { N = static_cast<int>(adj_list.size()); depth = std::vector<int>(N, 0); subtree_size = std::vector<int>(N, 0); for (logN = 0; (1 << logN) < N; ++logN) { } parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0)); dfs(adj_list, 0, 0); for (int i = 1; i < logN; ++i) { for (int j = 0; j < N; ++j) { parent[i][j] = parent[i - 1][parent[i - 1][j]]; } } } static int getLowestCommonAncestor(int X, int Y) { if (depth[X] < depth[Y]) { std::swap(X, Y); } for (int i = logN - 1; i >= 0; --i) { if (depth[parent[i][X]] >= depth[Y]) { X = parent[i][X]; } } if (X == Y) { return X; } for (int i = logN - 1; i >= 0; --i) { if (parent[i][X] != parent[i][Y]) { X = parent[i][X]; Y = parent[i][Y]; } } return parent[0][X]; } static int getDistance(int X, int Y) { return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)]; } static int attractionsBehind(int X, int Y) { if (X == Y) { return N; } for (int i = logN - 1; i >= 0; --i) { if (depth[parent[i][X]] > depth[Y]) { X = parent[i][X]; } } if (Y == parent[0][X]) { return N - subtree_size[X]; } return subtree_size[Y]; } static void checkFunTour(const std::vector<int>& fun_tour) { if (static_cast<int>(fun_tour.size()) != N) { wrongAnswer("Invalid size"); } std::vector<bool> visited_attractions(N, false); for (int i = 0; i < N; ++i) { if (fun_tour[i] < 0 || fun_tour[i] >= N) { wrongAnswer("Invalid index"); } if (visited_attractions[fun_tour[i]]) { wrongAnswer("Repeated index"); } visited_attractions[fun_tour[i]] = true; } int last_travel_time = getDistance(fun_tour[0], fun_tour[1]); for (int i = 2; i < N; ++i) { int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]); if (travel_time > last_travel_time) { wrongAnswer("Tour is not fun"); } last_travel_time = travel_time; } } } // namespace tree_helper static int N, Q; int hoursRequired(int X, int Y) { if (--Q < 0) { wrongAnswer("Too many queries"); } if (X < 0 || X >= N || Y < 0 || Y >= N) { wrongAnswer("Invalid index"); } return tree_helper::getDistance(X, Y); } int attractionsBehind(int X, int Y) { if (--Q < 0) { wrongAnswer("Too many queries"); } if (X < 0 || X >= N || Y < 0 || Y >= N) { wrongAnswer("Invalid index"); } return tree_helper::attractionsBehind(X, Y); } int main() { assert(2 == scanf("%d %d", &N, &Q)); std::vector<std::vector<int>> adj_list(N); for (int i = 0; i < N - 1; ++i) { int A, B; assert(2 == scanf("%d %d", &A, &B)); adj_list[A].push_back(B); adj_list[B].push_back(A); } tree_helper::initializeTree(adj_list); std::vector<int> fun_tour = createFunTour(N, Q); tree_helper::checkFunTour(fun_tour); for (int i = 0; i < N; ++i) { printf("%d%c", fun_tour[i], " \n"[i == N - 1]); } return 0; }*/
#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...