QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414992#33. Cat in a treex-camp0 3ms11724kbC++171.9kb2024-05-20 06:41:552024-05-20 06:41:56

Judging History

你现在查看的是最新测评结果

  • [2024-05-20 06:41:56]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:11724kb
  • [2024-05-20 06:41:55]
  • 提交

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%