Submission #46574

#TimeUsernameProblemLanguageResultExecution timeMemory
46574qoo2p5Amusement Park (JOI17_amusement_park)C++17
100 / 100
812 ms237768 KiB
#include "Joi.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; static const int INF = (int) 1e9 + 1e6 + 123; static const ll LINF = (ll) 1e18 + 1e9 + 123; #define rep(i, s, t) for (auto i = (s); i < (t); ++(i)) #define per(i, s, t) for (auto i = (s); i >= (t); --(i)) #define all(x) (x).begin(), (x).end() #define sz(x) ((int) (x).size()) #define mp make_pair #define pb push_back static bool mini(auto &x, const auto &y) { if (y < x) { x = y; return 1; } return 0; } static bool maxi(auto &x, const auto &y) { if (y > x) { x = y; return 1; } return 0; } static const int N = 20005; static const int K = 60; static int n; static int p[N]; static vector<int> g[N]; static int get(int v) { return (p[v] == v ? v : (p[v] = get(p[v]))); } static bool unite(int u, int v) { u = get(u), v = get(v); if (u == v) { return 0; } p[u] = v; return 1; } static bool test(long long mask, int bit) { return mask & (1LL << bit); } static void add_edge(int u, int v) { g[u].pb(v); g[v].pb(u); } static int center; static int center_dist = INF; static int dist[N]; static void calc_dist(int v, int f = -1) { dist[v] = 0; for (int u : g[v]) { if (u == f) { continue; } calc_dist(u, v); maxi(dist[v], dist[u] + 1); } } static void find_center(int v, int f = -1, int up = 0) { int max_dist = max(up, dist[v]); if (mini(center_dist, max_dist)) { center = v; } multiset<int> q; for (int u : g[v]) { if (u == f) { continue; } q.insert(dist[u] + 2); } for (int u : g[v]) { if (u == f) { continue; } q.erase(q.find(dist[u] + 2)); int nup = up + 1; if (sz(q)) { maxi(nup, *q.rbegin()); } find_center(u, v, nup); q.insert(dist[u] + 2); } } static void make_root(int v, int f = -1) { p[v] = f; int ptr = 0; int pos = -1; for (int u : g[v]) { if (u == f) { pos = ptr; ptr++; continue; } make_root(u, v); ptr++; } if (pos != -1) { g[v].erase(g[v].begin() + pos); } } static int what[N]; static void periodic_color(int v, int c, int dir) { what[v] = c; for (int u : g[v]) { periodic_color(u, (c + dir + K) % K, dir); } } struct Tree { map<int, set<int>> edges; void dfs(int v, vector<int> &path, int f = -1) { if (f != -1) path.pb(v); for (int u : edges[v]) { if (u == f) { continue; } dfs(u, path, v); path.pb(v); } } int find_leaf(int deny) { for (auto &it : edges) { if (it.first == deny) continue; if (sz(it.second) == 1) { return it.first; } } assert(0); return -1; } int extract_leaf(int deny) { int v = find_leaf(deny); int u = *edges[v].begin(); edges[u].erase(v); edges.erase(v); return v; } void add_edge(int u, int v) { edges[u].insert(v); edges[v].insert(u); } }; static Tree wtf[N]; static void easy_find(int v) { if (sz(wtf[center].edges) == K) { return; } for (int u : g[v]) { wtf[center].add_edge(v, u); easy_find(u); if (sz(wtf[center].edges) == K) { return; } } } static void meow(int v) { if (wtf[v].edges.empty()) { wtf[v] = wtf[p[v]]; int col = what[wtf[v].extract_leaf(p[v])]; what[v] = col; wtf[v].add_edge(v, p[v]); } for (int u : g[v]) { meow(u); } } void Joi(int nn, int mm, int A[], int B[], long long x, int T) { n = nn; rep(i, 0, n) p[i] = i; rep(i, 0, mm) { if (unite(A[i], B[i])) { add_edge(A[i], B[i]); } } calc_dist(0); find_center(0); make_root(center); calc_dist(center); if (dist[center] >= K - 1) { periodic_color(center, 0, +1); } else { easy_find(center); int ptr = 0; for (auto &it : wtf[center].edges) { int u = it.first; what[u] = ptr++; if (u != center) wtf[u] = wtf[center]; } meow(center); rep(i, 0, n) { assert(sz(wtf[i].edges) == K); vector<bool> col(K); for (auto &it : wtf[i].edges) { int u = it.first; col[what[u]] = 1; } rep(i, 0, K) assert(col[i]); } } rep(i, 0, n) { MessageBoard(i, test(x, what[i])); } }
#include "Ioi.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; static const int INF = (int) 1e9 + 1e6 + 123; static const ll LINF = (ll) 1e18 + 1e9 + 123; #define rep(i, s, t) for (auto i = (s); i < (t); ++(i)) #define per(i, s, t) for (auto i = (s); i >= (t); --(i)) #define all(x) (x).begin(), (x).end() #define sz(x) ((int) (x).size()) #define mp make_pair #define pb push_back static bool mini(auto &x, const auto &y) { if (y < x) { x = y; return 1; } return 0; } static bool maxi(auto &x, const auto &y) { if (y > x) { x = y; return 1; } return 0; } static const int N = 20005; static const int K = 60; static int n; static int p[N]; static vector<int> g[N]; static int get(int v) { return (p[v] == v ? v : (p[v] = get(p[v]))); } static bool unite(int u, int v) { u = get(u), v = get(v); if (u == v) { return 0; } p[u] = v; return 1; } static bool test(long long mask, int bit) { return mask & (1LL << bit); } static void add_edge(int u, int v) { g[u].pb(v); g[v].pb(u); } static int center; static int center_dist = INF; static int dist[N]; static void calc_dist(int v, int f = -1) { dist[v] = 0; for (int u : g[v]) { if (u == f) { continue; } calc_dist(u, v); maxi(dist[v], dist[u] + 1); } } static void find_center(int v, int f = -1, int up = 0) { int max_dist = max(up, dist[v]); if (mini(center_dist, max_dist)) { center = v; } multiset<int> q; for (int u : g[v]) { if (u == f) { continue; } q.insert(dist[u] + 2); } for (int u : g[v]) { if (u == f) { continue; } q.erase(q.find(dist[u] + 2)); int nup = up + 1; if (sz(q)) { maxi(nup, *q.rbegin()); } find_center(u, v, nup); q.insert(dist[u] + 2); } } static void make_root(int v, int f = -1) { p[v] = f; int ptr = 0; int pos = -1; for (int u : g[v]) { if (u == f) { pos = ptr; ptr++; continue; } make_root(u, v); ptr++; } if (pos != -1) { g[v].erase(g[v].begin() + pos); } } static int what[N]; static void periodic_color(int v, int c, int dir) { what[v] = c; for (int u : g[v]) { periodic_color(u, (c + dir + K) % K, dir); } } struct Tree { map<int, set<int>> edges; void dfs(int v, vector<int> &path, int f = -1) { if (f != -1) path.pb(v); for (int u : edges[v]) { if (u == f) { continue; } dfs(u, path, v); path.pb(v); } } int find_leaf(int deny) { for (auto &it : edges) { if (it.first == deny) continue; if (sz(it.second) == 1) { return it.first; } } assert(0); return -1; } int extract_leaf(int deny) { int v = find_leaf(deny); int u = *edges[v].begin(); edges[u].erase(v); edges.erase(v); return v; } void add_edge(int u, int v) { edges[u].insert(v); edges[v].insert(u); } vector<int> get_path(int start) { vector<int> res; dfs(start, res); return res; } }; static Tree wtf[N]; static void easy_find(int v) { if (sz(wtf[center].edges) == K) { return; } for (int u : g[v]) { wtf[center].add_edge(v, u); easy_find(u); if (sz(wtf[center].edges) == K) { return; } } } static void meow(int v) { if (wtf[v].edges.empty()) { wtf[v] = wtf[p[v]]; int col = what[wtf[v].extract_leaf(p[v])]; what[v] = col; wtf[v].add_edge(v, p[v]); } for (int u : g[v]) { meow(u); } } ll know[K]; bool known() { rep(i, 0, K) { if (know[i] == -1) { return 0; } } return 1; } ll answer() { ll ans = 0; rep(i, 0, K) { ans += (know[i] << i); } return ans; } int v; void go(int to) { static int steps = 0; steps++; assert(steps <= 500); assert(0 <= to && to <= n - 1); int x = Move(to); v = to; know[what[v]] = x; } long long Ioi(int nn, int mm, int A[], int B[], int vv, int num, int T) { rep(i, 0, K) know[i] = -1; n = nn; rep(i, 0, n) p[i] = i; rep(i, 0, mm) { if (unite(A[i], B[i])) { add_edge(A[i], B[i]); } } calc_dist(0); find_center(0); make_root(center); calc_dist(center); v = vv; if (dist[center] >= K - 1) { periodic_color(center, 0, +1); know[what[v]] = num; while (p[v] != -1) { go(p[v]); if (known()) { break; } } while (!known()) { assert(sz(g[v])); int u = *max_element(all(g[v]), [&] (int x, int y) { return dist[x] < dist[y]; }); go(u); } } else { easy_find(center); int ptr = 0; for (auto &it : wtf[center].edges) { int u = it.first; what[u] = ptr++; if (u != center) wtf[u] = wtf[center]; } meow(center); rep(i, 0, n) { vector<bool> col(K); for (auto &it : wtf[i].edges) { int u = it.first; col[what[u]] = 1; } } vector<int> path = wtf[v].get_path(v); for (int u : path) { go(u); } } return answer(); }

Compilation message (stderr)

Ioi.cpp:54:13: warning: 'bool test(long long int, int)' defined but not used [-Wunused-function]
 static bool test(long long mask, int bit) {
             ^~~~
#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...