# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
630815 | 2022-08-17T07:03:42 Z | SanguineChameleon | Cat in a tree (BOI17_catinatree) | C++14 | 264 ms | 53288 KB |
// BEGIN BOILERPLATE CODE #include <bits/stdc++.h> using namespace std; #ifdef KAMIRULEZ const bool kami_loc = true; const long long kami_seed = 69420; #else const bool kami_loc = false; const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count(); #endif const string kami_fi = "kamirulez.inp"; const string kami_fo = "kamirulez.out"; mt19937_64 kami_gen(kami_seed); long long rand_range(long long rmin, long long rmax) { uniform_int_distribution<long long> rdist(rmin, rmax); return rdist(kami_gen); } void file_io(string fi, string fo) { if (fi != "" && (!kami_loc || fi == kami_fi)) { freopen(fi.c_str(), "r", stdin); } if (fo != "" && (!kami_loc || fo == kami_fo)) { freopen(fo.c_str(), "w", stdout); } } void set_up() { if (kami_loc) { file_io(kami_fi, kami_fo); } ios_base::sync_with_stdio(0); cin.tie(0); } void just_do_it(); void just_exec_it() { if (kami_loc) { auto pstart = chrono::steady_clock::now(); just_do_it(); auto pend = chrono::steady_clock::now(); long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count(); string bar(50, '='); cout << '\n' << bar << '\n'; cout << "Time: " << ptime << " ms" << '\n'; } else { just_do_it(); } } int main() { set_up(); just_exec_it(); return 0; } // END BOILERPLATE CODE // BEGIN MAIN CODE const int ms = 2e5 + 20; const int st = 20; vector<int> ch[ms]; vector<int> adj[ms]; int de[ms]; int a[ms]; int lg[ms * 2]; int h[ms * 2][st]; int pt[ms]; bool f[ms]; int tz; void dfs(int u) { tz++; pt[u] = tz; h[tz][0] = de[u]; for (auto v: ch[u]) { de[v] = de[u] + 1; dfs(v); tz++; h[tz][0] = de[u]; } } bool cmp(int x, int y) { return de[x] > de[y]; } int dist(int u, int v) { int lt = pt[u]; int rt = pt[v]; if (lt > rt) { swap(lt, rt); } int k = lg[rt - lt + 1]; return de[u] + de[v] - 2 * min(h[lt][k], h[rt - (1 << k) + 1][k]); } void just_do_it() { lg[1] = 0; for (int i = 2; i < ms * 2; i++) { lg[i] = lg[i / 2] + 1; } int n, d; cin >> n >> d; for (int i = 2; i <= n; i++) { int u; cin >> u; u++; ch[u].push_back(i); adj[u].push_back(i); adj[i].push_back(u); } dfs(1); for (int k = 1; k < st; k++) { for (int i = 1; i + (1 << k) - 1 <= n * 2 - 1; i++) { h[i][k] = min(h[i][k - 1], h[i + (1 << (k - 1))][k - 1]); } } iota(a + 1, a + n + 1, 1); sort(a + 1, a + n + 1, cmp); deque<int> p; int res = 0; for (int i = 1; i <= n; i++) { int u = a[i]; if (f[u]) { continue; } bool ok = true; for (auto x: p) { if (dist(x, u) < d) { ok = false; break; } } if (!ok) { continue; } p.push_back(u); res++; if (p.size() % 400 == 0) { deque<int> z; for (auto x: p) { f[x] = true; z.push_back(0); } while (!p.empty()) { int u = p.front(); int cd = z.front(); p.pop_front(); z.pop_front(); if (cd == d - 1) { continue; } for (auto v: adj[u]) { if (!f[v]) { f[v] = true; p.push_back(v); z.push_back(cd + 1); } } } } } cout << res; } // END MAIN CODE
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11220 KB | Output is correct |
2 | Correct | 6 ms | 11220 KB | Output is correct |
3 | Correct | 6 ms | 11220 KB | Output is correct |
4 | Correct | 6 ms | 11204 KB | Output is correct |
5 | Correct | 6 ms | 11220 KB | Output is correct |
6 | Correct | 6 ms | 11220 KB | Output is correct |
7 | Correct | 6 ms | 11220 KB | Output is correct |
8 | Correct | 7 ms | 11212 KB | Output is correct |
9 | Correct | 7 ms | 11220 KB | Output is correct |
10 | Correct | 6 ms | 11220 KB | Output is correct |
11 | Correct | 6 ms | 11220 KB | Output is correct |
12 | Correct | 7 ms | 11220 KB | Output is correct |
13 | Correct | 6 ms | 11220 KB | Output is correct |
14 | Correct | 6 ms | 11220 KB | Output is correct |
15 | Correct | 6 ms | 11320 KB | Output is correct |
16 | Correct | 5 ms | 11220 KB | Output is correct |
17 | Correct | 6 ms | 11220 KB | Output is correct |
18 | Correct | 6 ms | 11220 KB | Output is correct |
19 | Correct | 6 ms | 11232 KB | Output is correct |
20 | Correct | 8 ms | 11220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11220 KB | Output is correct |
2 | Correct | 6 ms | 11220 KB | Output is correct |
3 | Correct | 6 ms | 11220 KB | Output is correct |
4 | Correct | 6 ms | 11204 KB | Output is correct |
5 | Correct | 6 ms | 11220 KB | Output is correct |
6 | Correct | 6 ms | 11220 KB | Output is correct |
7 | Correct | 6 ms | 11220 KB | Output is correct |
8 | Correct | 7 ms | 11212 KB | Output is correct |
9 | Correct | 7 ms | 11220 KB | Output is correct |
10 | Correct | 6 ms | 11220 KB | Output is correct |
11 | Correct | 6 ms | 11220 KB | Output is correct |
12 | Correct | 7 ms | 11220 KB | Output is correct |
13 | Correct | 6 ms | 11220 KB | Output is correct |
14 | Correct | 6 ms | 11220 KB | Output is correct |
15 | Correct | 6 ms | 11320 KB | Output is correct |
16 | Correct | 5 ms | 11220 KB | Output is correct |
17 | Correct | 6 ms | 11220 KB | Output is correct |
18 | Correct | 6 ms | 11220 KB | Output is correct |
19 | Correct | 6 ms | 11232 KB | Output is correct |
20 | Correct | 8 ms | 11220 KB | Output is correct |
21 | Correct | 7 ms | 11732 KB | Output is correct |
22 | Correct | 7 ms | 11348 KB | Output is correct |
23 | Correct | 8 ms | 11348 KB | Output is correct |
24 | Correct | 7 ms | 11476 KB | Output is correct |
25 | Correct | 10 ms | 11476 KB | Output is correct |
26 | Correct | 7 ms | 11536 KB | Output is correct |
27 | Correct | 7 ms | 11476 KB | Output is correct |
28 | Correct | 8 ms | 11604 KB | Output is correct |
29 | Correct | 8 ms | 11604 KB | Output is correct |
30 | Correct | 7 ms | 11604 KB | Output is correct |
31 | Correct | 7 ms | 11604 KB | Output is correct |
32 | Correct | 8 ms | 11604 KB | Output is correct |
33 | Correct | 7 ms | 11520 KB | Output is correct |
34 | Correct | 7 ms | 11536 KB | Output is correct |
35 | Correct | 6 ms | 11604 KB | Output is correct |
36 | Correct | 7 ms | 11604 KB | Output is correct |
37 | Correct | 7 ms | 11576 KB | Output is correct |
38 | Correct | 7 ms | 11604 KB | Output is correct |
39 | Correct | 7 ms | 11604 KB | Output is correct |
40 | Correct | 8 ms | 11732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11220 KB | Output is correct |
2 | Correct | 6 ms | 11220 KB | Output is correct |
3 | Correct | 6 ms | 11220 KB | Output is correct |
4 | Correct | 6 ms | 11204 KB | Output is correct |
5 | Correct | 6 ms | 11220 KB | Output is correct |
6 | Correct | 6 ms | 11220 KB | Output is correct |
7 | Correct | 6 ms | 11220 KB | Output is correct |
8 | Correct | 7 ms | 11212 KB | Output is correct |
9 | Correct | 7 ms | 11220 KB | Output is correct |
10 | Correct | 6 ms | 11220 KB | Output is correct |
11 | Correct | 6 ms | 11220 KB | Output is correct |
12 | Correct | 7 ms | 11220 KB | Output is correct |
13 | Correct | 6 ms | 11220 KB | Output is correct |
14 | Correct | 6 ms | 11220 KB | Output is correct |
15 | Correct | 6 ms | 11320 KB | Output is correct |
16 | Correct | 5 ms | 11220 KB | Output is correct |
17 | Correct | 6 ms | 11220 KB | Output is correct |
18 | Correct | 6 ms | 11220 KB | Output is correct |
19 | Correct | 6 ms | 11232 KB | Output is correct |
20 | Correct | 8 ms | 11220 KB | Output is correct |
21 | Correct | 7 ms | 11732 KB | Output is correct |
22 | Correct | 7 ms | 11348 KB | Output is correct |
23 | Correct | 8 ms | 11348 KB | Output is correct |
24 | Correct | 7 ms | 11476 KB | Output is correct |
25 | Correct | 10 ms | 11476 KB | Output is correct |
26 | Correct | 7 ms | 11536 KB | Output is correct |
27 | Correct | 7 ms | 11476 KB | Output is correct |
28 | Correct | 8 ms | 11604 KB | Output is correct |
29 | Correct | 8 ms | 11604 KB | Output is correct |
30 | Correct | 7 ms | 11604 KB | Output is correct |
31 | Correct | 7 ms | 11604 KB | Output is correct |
32 | Correct | 8 ms | 11604 KB | Output is correct |
33 | Correct | 7 ms | 11520 KB | Output is correct |
34 | Correct | 7 ms | 11536 KB | Output is correct |
35 | Correct | 6 ms | 11604 KB | Output is correct |
36 | Correct | 7 ms | 11604 KB | Output is correct |
37 | Correct | 7 ms | 11576 KB | Output is correct |
38 | Correct | 7 ms | 11604 KB | Output is correct |
39 | Correct | 7 ms | 11604 KB | Output is correct |
40 | Correct | 8 ms | 11732 KB | Output is correct |
41 | Incorrect | 264 ms | 53288 KB | Output isn't correct |
42 | Halted | 0 ms | 0 KB | - |