oj.uz

답안 #373246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373246 2021-03-03T23:04:04 Z ijxjdjd Cat in a tree (BOI17_catinatree) C++14
0 / 100
 4 ms 5100 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;
const int MAXN = (int)(2e5);
bool blocked[MAXN];
int cnt[MAXN];
vector<int> adj[MAXN];
int ans = 0;
vector<int> pos;
void bk(int n, int d) {
    if (d == 0) {
        cnt[n]--;
        if (cnt[n] == 1) {
            pos.push_back(n);
        }
        return;
    }
    else {
        blocked[n] = true;
        for (int e : adj[n]) {
            if (!blocked[e]) {
                bk(e, d-1);
            }
        }
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, D;
	cin >> N >> D;
	FR(i, N-1) {
        int p;
        cin >> p;
        adj[i+1].push_back(p);
        cnt[i+1]++;
        adj[p].push_back(i+1);
        cnt[p]++;
	}
	FR(i, N) {
        if (cnt[i] == 1) {
            pos.push_back(i);
        }
	}
	while (pos.size()) {
        int nxt = pos.back();
        pos.pop_back();
        if (!blocked[nxt]) {
            ans++;
            bk(nxt, D);
        }
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Halted 0 ms 0 KB -