QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415087 | #33. Cat in a tree | x-camp | 0 | 3ms | 10020kb | C++17 | 3.6kb | 2024-05-20 09:33:45 | 2024-05-20 09:33:46 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#include <algorithm>
/*
centroid decomposition to solve Cat in Tree problem
*/
using namespace std;
#define INF (1e9)
const int MX = 200001; // Adjust the maximum number of nodes as needed
vector<int> adj[MX];
bool visited[MX];
int subtreeSize[MX];
int min_dist[MX];
vector<vector<pair<int, int>>> ancestors;
int N, D;
int dfs_depth;
vector<pair<int,int>> nodes;
int ans;
int dfs(int node, int parent, int depth = 1) {
subtreeSize[node] = 1;
for (int child : adj[node]) {
if (child != parent && !visited[child]) {
subtreeSize[node] += dfs(child, node, depth+1);
}
}
if (subtreeSize[node] == 1)
nodes.push_back({-depth,node});
return subtreeSize[node];
}
int findCentroid(int node, int parent, int treeSize) {
for (int child : adj[node]) {
if (child != parent && !visited[child]) {
if (subtreeSize[child] *2 >= treeSize)
return findCentroid(child, node, treeSize);
}
}
return node;
}
void get_dists(int node, int centroid, int parent = -1, int cur_dist = 1) {
for (int child : adj[node]) {
if (child == parent || visited[child]) { continue; }
// cur_dist++;
get_dists(child, centroid, node, cur_dist+1);
// cur_dist--;
}
ancestors[node].push_back({centroid, cur_dist});
}
int cnt = 0;
void decompose(int centroid) {
cnt ++;
for (int child : adj[centroid]) {
if (visited[child]) { continue; }
get_dists(child, centroid, centroid);
}
// Mark the centroid and its subtree as visited
visited[centroid] = true;
for (int child : adj[centroid]) {
if (!visited[child]) {
// Recursively decompose the subtrees
int subtreeSize = dfs(child, centroid,1);
int childCentroid = findCentroid(child, centroid, subtreeSize);
if (subtreeSize > 1)
decompose(childCentroid);
}
}
}
int centroidDecomposition(int root) {
int treeSize = dfs(root, -1);
int centroid = findCentroid(root, -1, treeSize);
// Process the centroid and its subtree
decompose(centroid);
return centroid;
}
void paintRed (int node) {
for (auto &[ancestor, dist] : ancestors[node]) {
if (dist < min_dist[ancestor])
min_dist[ancestor] = dist;
}
min_dist[node] = 0;
}
/* min distance from a node to any red note*/
int query(int node) {
int ans = min_dist[node];
for (auto &[ancestor, dist] : ancestors[node]) {
if (!dist) { continue; }
/*
* The distance between `node` and a red painted node is the sum of
* the distance from `node` to one of its ancestors (`dist`) and the
* distance from this ancestor to the nearest red node
* (`min_dist[ancestor]`).
*/
ans = min(ans, dist + min_dist[ancestor]);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> D;
for (int i = 1; i <= N - 1; ++i) {
int u;
cin >> u;
adj[i].push_back(u);
adj[u].push_back(i);
}
memset(min_dist, 0x3f, sizeof min_dist);
ancestors.assign(N+1, vector<pair<int, int>>());
centroidDecomposition(1);
sort(nodes.begin(), nodes.end());
for (int i=0; i<nodes.size(); i++) {
auto next = nodes[i];
if (query(next.second) >= D) {
paintRed(next.second);
ans++;
}
}
cout << ans ;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 2ms
memory: 9212kb
input:
10 2 0 0 2 2 0 3 4 7 2
output:
6
result:
ok single line: '6'
Test #2:
score: 11
Accepted
time: 0ms
memory: 10020kb
input:
10 3 0 0 2 1 4 4 3 1 7
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Wrong Answer
time: 3ms
memory: 10020kb
input:
12 1 0 0 1 3 1 0 2 1 3 2 2
output:
8
result:
wrong answer 1st lines differ - expected: '12', found: '8'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%