제출 #1215061

#제출 시각아이디문제언어결과실행 시간메모리
1215061madamadam3Cat in a tree (BOI17_catinatree)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define bg(x) (x).begin() #define en(x) (x).end() const int MAXN = 200'001, MAXLOG = 18; int n, d; vector<vector<int>> adj, up; vector<int> depth, tin, tout; int timer = 0; map<int, set<int>> depth_map; 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]; } // depth_map[depth[u]].push_back(tin[u]); depth_map[depth[u]].insert(u); 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)]; } // // how many nodes are there in the subtree of u at depth d // int nodes_depth(int u, int dpth) { // int upper =upper_bound(all(depth_map[dpth]), tout[u]) - bg(depth_map[dpth]); // int lower = lower_bound(all(depth_map[dpth]), tin[u]) - bg(depth_map[dpth]); // return upper - lower; // } 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 remove_near(int u, int tim, vector<bool> &vis) { if (tim > d) return; vis[u] = true; depth_map[depth[u]].erase(u); for (auto &v : adj[u]) { if (vis[v]) continue; remove_near(v, tim+1, vis); } } void task2() { // n <= 1500 int tl = 0; int cur_depth = *max_element(all(depth)); vector<bool> vis(n, false); while (cur_depth >= 0) { if (depth_map[cur_depth].size() == 0) { cur_depth--; continue; } int cur_node = *depth_map[cur_depth].begin(); remove_near(cur_node, 0, vis); 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...