oj.uz

답안 #974799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974799 2024-05-03T19:51:48 Z KasymK Cat in a tree (BOI17_catinatree) C++17
11 / 100
 1000 ms 3596 KB 
#include "bits/stdc++.h"

using namespace std;

const int N = 1e5 + 5;

int n, d;
int mx = INT_MIN;

vector<int> adj[N], bit;

int vis[N], dis[N];

int in_yakyn(int id){
    for(int i = 0; i < n; ++i)
        vis[i] = dis[i] = 0;
    queue<int> q;
    q.push(id);
    vis[id] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto i : adj[x])
            if(!vis[i]){
                vis[i] = 1;
                q.push(i);
                dis[i] = dis[x] + 1;
                if(bit[i])
                    return dis[i];
            }
    }
}

bool barla(){
    int cnt = count(bit.begin(), bit.end(), 1);
    if(cnt <= 1)
        return 1;
    for(int i = 0; i < n; ++i)
        if(bit[i] and in_yakyn(i) < d)
            return 0;
    return 1;
}

void f(int x){
    if(x == n){
        int cnt = count(bit.begin(), bit.end(), 1);
        if(barla())
            mx = max(mx, cnt);
        return;
    }
    for(int i = 0; i <= 1; ++i){
        bit[x] = i;
        f(x + 1);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d;
    for(int i = 1; i <= n - 1; ++i){
        int x;
        cin >> x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
    bit.resize(n);
    f(0);
    cout << mx << "\n";
    return 0;
}

Compilation message

catinatree.cpp: In function 'int in_yakyn(int)':
catinatree.cpp:17:16: warning: control reaches end of non-void function [-Wreturn-type]
   17 |     queue<int> q;
      |                ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 4 ms 3164 KB Output is correct
6 Correct 3 ms 3160 KB Output is correct
7 Correct 9 ms 3596 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct
9 Correct 115 ms 3396 KB Output is correct
10 Correct 20 ms 3164 KB Output is correct
11 Correct 115 ms 3388 KB Output is correct
12 Correct 64 ms 3388 KB Output is correct
13 Correct 53 ms 3392 KB Output is correct
14 Correct 16 ms 3416 KB Output is correct
15 Correct 20 ms 3416 KB Output is correct
16 Correct 113 ms 3392 KB Output is correct
17 Correct 25 ms 3164 KB Output is correct
18 Correct 20 ms 3164 KB Output is correct
19 Correct 22 ms 3164 KB Output is correct
20 Correct 20 ms 3420 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 4 ms 3164 KB Output is correct
6 Correct 3 ms 3160 KB Output is correct
7 Correct 9 ms 3596 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct
9 Correct 115 ms 3396 KB Output is correct
10 Correct 20 ms 3164 KB Output is correct
11 Correct 115 ms 3388 KB Output is correct
12 Correct 64 ms 3388 KB Output is correct
13 Correct 53 ms 3392 KB Output is correct
14 Correct 16 ms 3416 KB Output is correct
15 Correct 20 ms 3416 KB Output is correct
16 Correct 113 ms 3392 KB Output is correct
17 Correct 25 ms 3164 KB Output is correct
18 Correct 20 ms 3164 KB Output is correct
19 Correct 22 ms 3164 KB Output is correct
20 Correct 20 ms 3420 KB Output is correct
21 Execution timed out 1018 ms 3416 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 4 ms 3164 KB Output is correct
6 Correct 3 ms 3160 KB Output is correct
7 Correct 9 ms 3596 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct
9 Correct 115 ms 3396 KB Output is correct
10 Correct 20 ms 3164 KB Output is correct
11 Correct 115 ms 3388 KB Output is correct
12 Correct 64 ms 3388 KB Output is correct
13 Correct 53 ms 3392 KB Output is correct
14 Correct 16 ms 3416 KB Output is correct
15 Correct 20 ms 3416 KB Output is correct
16 Correct 113 ms 3392 KB Output is correct
17 Correct 25 ms 3164 KB Output is correct
18 Correct 20 ms 3164 KB Output is correct
19 Correct 22 ms 3164 KB Output is correct
20 Correct 20 ms 3420 KB Output is correct
21 Execution timed out 1018 ms 3416 KB Time limit exceeded
22 Halted 0 ms 0 KB -