# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
974506 | 2024-05-03T11:56:43 Z | KasymK | Cat in a tree (BOI17_catinatree) | C++17 | 1000 ms | 3788 KB |
#include "bits/stdc++.h" using namespace std; const int N = 1e5 + 5; vector<int> adj[N], vis; int n, d; int mx = INT_MIN; int marked[N], dis[N], see[N]; int in_yakyn(int x){ for (int i = 0; i < n; ++i) see[i] = dis[i] = 0; queue<int> q; q.push(x); see[x] = 1; while(!q.empty()){ int id = q.front(); q.pop(); for (int i : adj[id]) if (!see[i]){ dis[i] = dis[id] + 1; see[i] = 1; if(vis[i]) return dis[i]; q.push(i); } } } bool barla(){ int cnt = count(vis.begin(), vis.end(), 1); if(cnt <= 1) return 1; for (int i = 0; i < n; ++i) if(vis[i] and in_yakyn(i) < d) return 0; return 1; } void f(int x){ if(x == n){ int cnt = count(vis.begin(), vis.end(), 1); if(barla()) mx = max(mx, cnt); return; } for(int i = 0; i <= 1; ++i){ vis[x] = i; f(x + 1); } } int main() { scanf("%d%d", &n, &d); for(int i = 1; i <= n - 1; ++i) { int a; scanf("%d", &a); adj[a].push_back(i); adj[i].push_back(a); } vis.resize(n); f(0); printf("%d\n", mx); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3672 KB | Output is correct |
2 | Correct | 2 ms | 3676 KB | Output is correct |
3 | Correct | 2 ms | 3676 KB | Output is correct |
4 | Correct | 1 ms | 3676 KB | Output is correct |
5 | Correct | 3 ms | 3780 KB | Output is correct |
6 | Correct | 2 ms | 3780 KB | Output is correct |
7 | Correct | 7 ms | 3672 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 104 ms | 3676 KB | Output is correct |
10 | Correct | 19 ms | 3672 KB | Output is correct |
11 | Correct | 110 ms | 3764 KB | Output is correct |
12 | Correct | 63 ms | 3764 KB | Output is correct |
13 | Correct | 56 ms | 3756 KB | Output is correct |
14 | Correct | 15 ms | 3676 KB | Output is correct |
15 | Correct | 20 ms | 3676 KB | Output is correct |
16 | Correct | 103 ms | 3676 KB | Output is correct |
17 | Correct | 28 ms | 3676 KB | Output is correct |
18 | Correct | 20 ms | 3788 KB | Output is correct |
19 | Correct | 19 ms | 3676 KB | Output is correct |
20 | Correct | 18 ms | 3676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3672 KB | Output is correct |
2 | Correct | 2 ms | 3676 KB | Output is correct |
3 | Correct | 2 ms | 3676 KB | Output is correct |
4 | Correct | 1 ms | 3676 KB | Output is correct |
5 | Correct | 3 ms | 3780 KB | Output is correct |
6 | Correct | 2 ms | 3780 KB | Output is correct |
7 | Correct | 7 ms | 3672 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 104 ms | 3676 KB | Output is correct |
10 | Correct | 19 ms | 3672 KB | Output is correct |
11 | Correct | 110 ms | 3764 KB | Output is correct |
12 | Correct | 63 ms | 3764 KB | Output is correct |
13 | Correct | 56 ms | 3756 KB | Output is correct |
14 | Correct | 15 ms | 3676 KB | Output is correct |
15 | Correct | 20 ms | 3676 KB | Output is correct |
16 | Correct | 103 ms | 3676 KB | Output is correct |
17 | Correct | 28 ms | 3676 KB | Output is correct |
18 | Correct | 20 ms | 3788 KB | Output is correct |
19 | Correct | 19 ms | 3676 KB | Output is correct |
20 | Correct | 18 ms | 3676 KB | Output is correct |
21 | Execution timed out | 1031 ms | 3672 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 3672 KB | Output is correct |
2 | Correct | 2 ms | 3676 KB | Output is correct |
3 | Correct | 2 ms | 3676 KB | Output is correct |
4 | Correct | 1 ms | 3676 KB | Output is correct |
5 | Correct | 3 ms | 3780 KB | Output is correct |
6 | Correct | 2 ms | 3780 KB | Output is correct |
7 | Correct | 7 ms | 3672 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 104 ms | 3676 KB | Output is correct |
10 | Correct | 19 ms | 3672 KB | Output is correct |
11 | Correct | 110 ms | 3764 KB | Output is correct |
12 | Correct | 63 ms | 3764 KB | Output is correct |
13 | Correct | 56 ms | 3756 KB | Output is correct |
14 | Correct | 15 ms | 3676 KB | Output is correct |
15 | Correct | 20 ms | 3676 KB | Output is correct |
16 | Correct | 103 ms | 3676 KB | Output is correct |
17 | Correct | 28 ms | 3676 KB | Output is correct |
18 | Correct | 20 ms | 3788 KB | Output is correct |
19 | Correct | 19 ms | 3676 KB | Output is correct |
20 | Correct | 18 ms | 3676 KB | Output is correct |
21 | Execution timed out | 1031 ms | 3672 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |