QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#414992 | #33. Cat in a tree | x-camp | 0 | 3ms | 11724kb | C++17 | 1.9kb | 2024-05-20 06:41:55 | 2024-05-20 06:41:56 |
Judging History
answer
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#define MX 200002
using namespace std;
vector<int> adj[MX];
int N,D;
int dep[MX];
set<pair<int,int>> nodes;
set<pair<int,int>>::iterator ptr[MX];
bool removed[MX];
int parent[MX];
bool visited[MX];
bool leaf[MX];
void dfs(int u, int par, int depth) {
parent[u] = par;
dep[u] = depth;
if (adj[u].size() == 1) leaf[u] = true;
auto it = nodes.insert({depth,u}).first;
ptr[u] = it;
for (auto v: adj[u]) {
if (v != par) {
dfs(v, u, depth+1);
}
}
}
bool dfs_maxD(int u, int par, int depth, bool mark) {
if (depth >= D ) {
return false;
}
int leafcnt = 0;
for (auto v: adj[u]) {
if (v != par && !visited[v]) {
//bool tmp = dfs_maxD(v, u, depth+1, mark);
if (dfs_maxD(v, u, depth+1, mark)) leafcnt ++;
}
}
if (!removed[u]) {
nodes.erase(ptr[u]);
removed[u] = true;
}
if (mark || leafcnt <=1 ) //mark the subtree as visited
visited[u] = true;
return leafcnt <= 1;
}
int main() {
cin >> N >> D;
for (int i=1; i<N; i++) {
int a;
cin >> a;
adj[i].push_back(a);
adj[a].push_back(i);
}
dfs(0,-1, 0);
int ans = 0;
while (!nodes.empty()) {
auto &[d, node] = *nodes.rbegin();
int cur = node;
// cout << "removed " << cur << endl;
for (int i=1; i<=(D-1)/2; i++) {
if (parent[cur] != -1)
cur = parent[cur];
else
break;
}
dfs_maxD(cur, parent[cur], 0, true); //take care of subtree
dfs_maxD(cur, -1, (D-1)/2, false);
ans++;
}
cout << ans;
return 0;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 11
Accepted
time: 3ms
memory: 10764kb
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: 2ms
memory: 10924kb
input:
10 3 0 0 2 1 4 4 3 1 7
output:
4
result:
ok single line: '4'
Test #3:
score: 11
Accepted
time: 0ms
memory: 10628kb
input:
12 1 0 0 1 3 1 0 2 1 3 2 2
output:
12
result:
ok single line: '12'
Test #4:
score: 11
Accepted
time: 0ms
memory: 11720kb
input:
12 4 0 0 1 2 0 0 4 7 7 9 10
output:
3
result:
ok single line: '3'
Test #5:
score: 11
Accepted
time: 2ms
memory: 10632kb
input:
14 2 0 1 2 3 0 1 5 1 4 0 3 11 9
output:
8
result:
ok single line: '8'
Test #6:
score: 11
Accepted
time: 0ms
memory: 10832kb
input:
14 4 0 0 2 3 4 2 6 3 6 9 3 3 2
output:
3
result:
ok single line: '3'
Test #7:
score: 11
Accepted
time: 2ms
memory: 11096kb
input:
16 2 0 0 0 1 2 3 2 6 6 0 4 11 0 12 2
output:
11
result:
ok single line: '11'
Test #8:
score: 11
Accepted
time: 2ms
memory: 11372kb
input:
16 3 0 0 0 3 2 2 0 2 8 4 6 11 8 3 5
output:
6
result:
ok single line: '6'
Test #9:
score: 11
Accepted
time: 2ms
memory: 11724kb
input:
18 1 0 0 2 2 2 1 0 3 1 4 2 2 12 0 6 10 13
output:
18
result:
ok single line: '18'
Test #10:
score: 0
Time Limit Exceeded
input:
18 5 0 0 2 1 0 2 6 5 8 5 0 8 5 4 12 7 10
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%