# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
257476 | 2020-08-04T10:29:37 Z | islingr | Amusement Park (JOI17_amusement_park) | C++17 | 0 ms | 0 KB |
#include "Ioi.h" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (auto i = (a); i < (b); ++i) #define all(x) begin(x), end(x) using ll = long long; namespace { const int N = 1 << 14, B = 60; int nxt[N]; int head(int u) { return nxt[u] != u ? nxt[u] = head(nxt[u]) : u; } bool unite(int u, int v) { u = head(u); v = head(v); if (u == v) return 0; nxt[u] = v; return 1; } vector<int> g[N]; int p[N], in[N], out[N], timer = 0; void init(int u) { in[u] = timer++; for (int v : g[u]) { g[v].erase(find(all(g[v]), u)); p[v] = u; init(v); } out[u] = timer; } ll cur = 0, x = 0; bool add(int u, ll z) { int s = in[u] % B; cur |= 1ll << s; x |= z << s; return __builtin_popcountll(cur) == B; } bool dfs(int u, int z) { if (add(u, z)) return true; for (int v : g[u]) { if (dfs(v, Move(v))) return true; Move(u); } return false; } } ll Ioi(int n, int m, int a[], int b[], int P, int V, int T) { rep(u, 0, n) nxt[u] = u; rep(e, 0, m) { if (unite(a[e], b[e])) { g[a[e]].push_back(b[e]); g[b[e]].push_back(a[e]); } } init(0); if (out[P] - in[P] < B) { int right = out[P]; while (right - in[P] < B) V = Move(p[P]), P = p[P]; } dfs(P, V); return x; }