Submission #1215084

#TimeUsernameProblemLanguageResultExecution timeMemory
1215084madamadam3Cat in a tree (BOI17_catinatree)C++20
51 / 100
630 ms589824 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 200'001, MAXLOG = 18; int n, d; vector<vector<int>> adj, up; vector<int> depth, tin, tout; int timer = 0; void dfs(int u, int p) { tin[u] = timer++; if (u == 0) depth[u] = 0; else depth[u] = depth[p] + 1; up[u][0] = p; for (int i = 1; i < MAXLOG; i++) { up[u][i] = up[up[u][i - 1]][i-1]; } for (auto &v : adj[u]) { if (v == p) continue; dfs(v, u); } tout[u] = timer; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int find_lca(int u, int v) { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = MAXLOG - 1; i >= 0; i--) { if (!is_ancestor(up[u][i], v)) { u = up[u][i]; } } return up[u][0]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[find_lca(u, v)]; } void task1() { // n <= 18 int most = 0; for (int mask = 0; mask < (1 << n); mask++) { vector<int> active; for (int bit = 0; bit < n; bit++) if (mask & (1 << bit)) active.push_back(bit); bool valid = true; for (auto &u : active) { for (auto &v : active) { if (u == v) continue; valid = valid && dist(u, v) >= d; } } if (valid) most = max(most, (int) active.size()); } cout << most; } void task2() { // n <= 1500 vector<vector<int>> dm(n, vector<int>(n, 0)); vector<set<int>> close(n); vector<bool> used(n, false); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; dm[i][j] = dist(i, j); if (dm[i][j] >= 1 && dm[i][j] < d) { close[i].insert(j); } } } auto least_near = [&]() { int best = -1, amt = -1; for (int i = 0; i < n; i++) { if (used[i]) continue; // if (close[i].size() >= amt) continue; if (depth[i] <= amt) continue; best = i; amt = depth[i]; } return best; }; int tl = 0; while (least_near() >= 0) { int cur = least_near(); used[cur] = true; set<int> near = close[cur]; for (auto &el : near) { used[el] = true; for (int i = 0; i < n; i++) { if (used[i]) continue; close[i].erase(el); } } tl++; } cout << tl; } void task3() { // n <= 2×10⁵ } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> d; adj.assign(n, vector<int>()); for (int i = 1; i < n; i++) { int xi; cin >> xi; adj[i].push_back(xi); adj[xi].push_back(i); } up.assign(n, vector<int>(MAXLOG, 0)); tin.assign(n, -1); tout.assign(n, -1); depth.assign(n, -1); dfs(0, 0); task2(); // if (n <= 18) task1(); // else if (n <= 1500) task2(); // else task3(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...