# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
974470 | 2024-05-03T11:22:06 Z | KasymK | Cat in a tree (BOI17_catinatree) | C++17 | 1000 ms | 3920 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) { // if (poz) { // cout <<"--> " << x; // exit(0); // } 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(); // if (poz == 1) { // cout << "ll-> " << to << "\n"; // } q.pop(); for (int i : adj[to]) { if (vis1[i]) continue; dis[i] = dis[to] + 1; q.push(i); vis1[i] = 1; if (vis[i]) { // if (poz) { // cout << " men " << i << " " << x << " " << dis[i] << "\n"; //// exit(0); // // } return dis[i]; } } } assert (1 == -1); } bool barla() { int cnt = count(vis.begin(), vis.end(), 1); if(cnt <= 1) return true; if (vis[0] == 0 and vis[1] == 0 and vis[2] == 1 and vis[3] == 1) { poz = 1; // cout << " kk --> " << in_yakyn (3); // << " " << in_yakyn (2); // exit(0); } 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) { if (vis[i]) ret++; } 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() { // freopen ("input.txt", "r", stdin); 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
# | Verdict | Execution time | Memory | 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 | 2 ms | 3676 KB | Output is correct |
6 | Correct | 2 ms | 3672 KB | Output is correct |
7 | Correct | 7 ms | 3676 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 111 ms | 3676 KB | Output is correct |
10 | Correct | 19 ms | 3676 KB | Output is correct |
11 | Correct | 119 ms | 3920 KB | Output is correct |
12 | Correct | 63 ms | 3672 KB | Output is correct |
13 | Correct | 57 ms | 3676 KB | Output is correct |
14 | Correct | 16 ms | 3828 KB | Output is correct |
15 | Correct | 19 ms | 3676 KB | Output is correct |
16 | Correct | 111 ms | 3764 KB | Output is correct |
17 | Correct | 23 ms | 3676 KB | Output is correct |
18 | Correct | 18 ms | 3676 KB | Output is correct |
19 | Correct | 21 ms | 3676 KB | Output is correct |
20 | Correct | 18 ms | 3676 KB | Output is correct |
# | Verdict | Execution time | Memory | 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 | 2 ms | 3676 KB | Output is correct |
6 | Correct | 2 ms | 3672 KB | Output is correct |
7 | Correct | 7 ms | 3676 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 111 ms | 3676 KB | Output is correct |
10 | Correct | 19 ms | 3676 KB | Output is correct |
11 | Correct | 119 ms | 3920 KB | Output is correct |
12 | Correct | 63 ms | 3672 KB | Output is correct |
13 | Correct | 57 ms | 3676 KB | Output is correct |
14 | Correct | 16 ms | 3828 KB | Output is correct |
15 | Correct | 19 ms | 3676 KB | Output is correct |
16 | Correct | 111 ms | 3764 KB | Output is correct |
17 | Correct | 23 ms | 3676 KB | Output is correct |
18 | Correct | 18 ms | 3676 KB | Output is correct |
19 | Correct | 21 ms | 3676 KB | Output is correct |
20 | Correct | 18 ms | 3676 KB | Output is correct |
21 | Execution timed out | 1066 ms | 3676 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | 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 | 2 ms | 3676 KB | Output is correct |
6 | Correct | 2 ms | 3672 KB | Output is correct |
7 | Correct | 7 ms | 3676 KB | Output is correct |
8 | Correct | 5 ms | 3676 KB | Output is correct |
9 | Correct | 111 ms | 3676 KB | Output is correct |
10 | Correct | 19 ms | 3676 KB | Output is correct |
11 | Correct | 119 ms | 3920 KB | Output is correct |
12 | Correct | 63 ms | 3672 KB | Output is correct |
13 | Correct | 57 ms | 3676 KB | Output is correct |
14 | Correct | 16 ms | 3828 KB | Output is correct |
15 | Correct | 19 ms | 3676 KB | Output is correct |
16 | Correct | 111 ms | 3764 KB | Output is correct |
17 | Correct | 23 ms | 3676 KB | Output is correct |
18 | Correct | 18 ms | 3676 KB | Output is correct |
19 | Correct | 21 ms | 3676 KB | Output is correct |
20 | Correct | 18 ms | 3676 KB | Output is correct |
21 | Execution timed out | 1066 ms | 3676 KB | Time limit exceeded |
22 | Halted | 0 ms | 0 KB | - |