# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
974481 | 2024-05-03T11:32:33 Z | KasymK | Cat in a tree (BOI17_catinatree) | C++17 | 1000 ms | 3928 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], vis1[N]; int poz = 0; int in_yakyn(int x){ queue <int> q; for (int i = 0; i < n; ++i) vis1[i] = dis[i] = 0; q.push(x); vis1[x] = 1; while(!q.empty()){ int to = q.front(); q.pop(); for (int i : adj[to]) if (!vis1[i]){ dis[i] = dis[to] + 1; q.push(i); vis1[i] = 1; if (vis[i]) return dis[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]) if(in_yakyn(i) < d) return 0; return 1; } int sana(){ int ret = 0; for (int i = 0; i < n; ++i) ret += vis[i]; return ret; } void f(int x){ if(x == n){ if(barla()) mx = max(mx, sana()); 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 | 1 ms | 3672 KB | Output is correct |
2 | Correct | 1 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 | 4 ms | 3672 KB | Output is correct |
6 | Correct | 2 ms | 3676 KB | Output is correct |
7 | Correct | 7 ms | 3676 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 119 ms | 3752 KB | Output is correct |
10 | Correct | 17 ms | 3928 KB | Output is correct |
11 | Correct | 108 ms | 3756 KB | Output is correct |
12 | Correct | 64 ms | 3928 KB | Output is correct |
13 | Correct | 54 ms | 3928 KB | Output is correct |
14 | Correct | 15 ms | 3676 KB | Output is correct |
15 | Correct | 17 ms | 3672 KB | Output is correct |
16 | Correct | 110 ms | 3752 KB | Output is correct |
17 | Correct | 23 ms | 3676 KB | Output is correct |
18 | Correct | 17 ms | 3676 KB | Output is correct |
19 | Correct | 17 ms | 3676 KB | Output is correct |
20 | Correct | 17 ms | 3776 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 3672 KB | Output is correct |
2 | Correct | 1 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 | 4 ms | 3672 KB | Output is correct |
6 | Correct | 2 ms | 3676 KB | Output is correct |
7 | Correct | 7 ms | 3676 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 119 ms | 3752 KB | Output is correct |
10 | Correct | 17 ms | 3928 KB | Output is correct |
11 | Correct | 108 ms | 3756 KB | Output is correct |
12 | Correct | 64 ms | 3928 KB | Output is correct |
13 | Correct | 54 ms | 3928 KB | Output is correct |
14 | Correct | 15 ms | 3676 KB | Output is correct |
15 | Correct | 17 ms | 3672 KB | Output is correct |
16 | Correct | 110 ms | 3752 KB | Output is correct |
17 | Correct | 23 ms | 3676 KB | Output is correct |
18 | Correct | 17 ms | 3676 KB | Output is correct |
19 | Correct | 17 ms | 3676 KB | Output is correct |
20 | Correct | 17 ms | 3776 KB | Output is correct |
21 | Execution timed out | 1052 ms | 3676 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 3672 KB | Output is correct |
2 | Correct | 1 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 | 4 ms | 3672 KB | Output is correct |
6 | Correct | 2 ms | 3676 KB | Output is correct |
7 | Correct | 7 ms | 3676 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 119 ms | 3752 KB | Output is correct |
10 | Correct | 17 ms | 3928 KB | Output is correct |
11 | Correct | 108 ms | 3756 KB | Output is correct |
12 | Correct | 64 ms | 3928 KB | Output is correct |
13 | Correct | 54 ms | 3928 KB | Output is correct |
14 | Correct | 15 ms | 3676 KB | Output is correct |
15 | Correct | 17 ms | 3672 KB | Output is correct |
16 | Correct | 110 ms | 3752 KB | Output is correct |
17 | Correct | 23 ms | 3676 KB | Output is correct |
18 | Correct | 17 ms | 3676 KB | Output is correct |
19 | Correct | 17 ms | 3676 KB | Output is correct |
20 | Correct | 17 ms | 3776 KB | Output is correct |
21 | Execution timed out | 1052 ms | 3676 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |