# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
630824 | 2022-08-17T07:19:31 Z | SanguineChameleon | Cat in a tree (BOI17_catinatree) | C++14 | 598 ms | 60324 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]; bool g[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; 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 (g[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) { for (int i = 1; i <= n; i++) { f[i] = false; } 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]) { g[v] = true; 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 | 5 ms | 11220 KB | Output is correct |
2 | Correct | 5 ms | 11220 KB | Output is correct |
3 | Correct | 5 ms | 11220 KB | Output is correct |
4 | Correct | 6 ms | 11220 KB | Output is correct |
5 | Correct | 7 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 | 6 ms | 11312 KB | Output is correct |
9 | Correct | 6 ms | 11312 KB | Output is correct |
10 | Correct | 6 ms | 11224 KB | Output is correct |
11 | Correct | 6 ms | 11220 KB | Output is correct |
12 | Correct | 6 ms | 11220 KB | Output is correct |
13 | Correct | 6 ms | 11320 KB | Output is correct |
14 | Correct | 6 ms | 11304 KB | Output is correct |
15 | Correct | 5 ms | 11220 KB | Output is correct |
16 | Correct | 6 ms | 11208 KB | Output is correct |
17 | Correct | 7 ms | 11308 KB | Output is correct |
18 | Correct | 6 ms | 11220 KB | Output is correct |
19 | Correct | 6 ms | 11220 KB | Output is correct |
20 | Correct | 6 ms | 11220 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 11220 KB | Output is correct |
2 | Correct | 5 ms | 11220 KB | Output is correct |
3 | Correct | 5 ms | 11220 KB | Output is correct |
4 | Correct | 6 ms | 11220 KB | Output is correct |
5 | Correct | 7 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 | 6 ms | 11312 KB | Output is correct |
9 | Correct | 6 ms | 11312 KB | Output is correct |
10 | Correct | 6 ms | 11224 KB | Output is correct |
11 | Correct | 6 ms | 11220 KB | Output is correct |
12 | Correct | 6 ms | 11220 KB | Output is correct |
13 | Correct | 6 ms | 11320 KB | Output is correct |
14 | Correct | 6 ms | 11304 KB | Output is correct |
15 | Correct | 5 ms | 11220 KB | Output is correct |
16 | Correct | 6 ms | 11208 KB | Output is correct |
17 | Correct | 7 ms | 11308 KB | Output is correct |
18 | Correct | 6 ms | 11220 KB | Output is correct |
19 | Correct | 6 ms | 11220 KB | Output is correct |
20 | Correct | 6 ms | 11220 KB | Output is correct |
21 | Correct | 6 ms | 11604 KB | Output is correct |
22 | Correct | 6 ms | 11328 KB | Output is correct |
23 | Correct | 6 ms | 11416 KB | Output is correct |
24 | Correct | 6 ms | 11348 KB | Output is correct |
25 | Correct | 7 ms | 11476 KB | Output is correct |
26 | Correct | 7 ms | 11528 KB | Output is correct |
27 | Correct | 7 ms | 11476 KB | Output is correct |
28 | Correct | 6 ms | 11604 KB | Output is correct |
29 | Correct | 7 ms | 11604 KB | Output is correct |
30 | Correct | 8 ms | 11604 KB | Output is correct |
31 | Correct | 6 ms | 11604 KB | Output is correct |
32 | Correct | 6 ms | 11616 KB | Output is correct |
33 | Correct | 6 ms | 11604 KB | Output is correct |
34 | Correct | 7 ms | 11604 KB | Output is correct |
35 | Correct | 6 ms | 11604 KB | Output is correct |
36 | Correct | 6 ms | 11604 KB | Output is correct |
37 | Correct | 7 ms | 11604 KB | Output is correct |
38 | Correct | 6 ms | 11600 KB | Output is correct |
39 | Correct | 7 ms | 11604 KB | Output is correct |
40 | Correct | 7 ms | 11604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 11220 KB | Output is correct |
2 | Correct | 5 ms | 11220 KB | Output is correct |
3 | Correct | 5 ms | 11220 KB | Output is correct |
4 | Correct | 6 ms | 11220 KB | Output is correct |
5 | Correct | 7 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 | 6 ms | 11312 KB | Output is correct |
9 | Correct | 6 ms | 11312 KB | Output is correct |
10 | Correct | 6 ms | 11224 KB | Output is correct |
11 | Correct | 6 ms | 11220 KB | Output is correct |
12 | Correct | 6 ms | 11220 KB | Output is correct |
13 | Correct | 6 ms | 11320 KB | Output is correct |
14 | Correct | 6 ms | 11304 KB | Output is correct |
15 | Correct | 5 ms | 11220 KB | Output is correct |
16 | Correct | 6 ms | 11208 KB | Output is correct |
17 | Correct | 7 ms | 11308 KB | Output is correct |
18 | Correct | 6 ms | 11220 KB | Output is correct |
19 | Correct | 6 ms | 11220 KB | Output is correct |
20 | Correct | 6 ms | 11220 KB | Output is correct |
21 | Correct | 6 ms | 11604 KB | Output is correct |
22 | Correct | 6 ms | 11328 KB | Output is correct |
23 | Correct | 6 ms | 11416 KB | Output is correct |
24 | Correct | 6 ms | 11348 KB | Output is correct |
25 | Correct | 7 ms | 11476 KB | Output is correct |
26 | Correct | 7 ms | 11528 KB | Output is correct |
27 | Correct | 7 ms | 11476 KB | Output is correct |
28 | Correct | 6 ms | 11604 KB | Output is correct |
29 | Correct | 7 ms | 11604 KB | Output is correct |
30 | Correct | 8 ms | 11604 KB | Output is correct |
31 | Correct | 6 ms | 11604 KB | Output is correct |
32 | Correct | 6 ms | 11616 KB | Output is correct |
33 | Correct | 6 ms | 11604 KB | Output is correct |
34 | Correct | 7 ms | 11604 KB | Output is correct |
35 | Correct | 6 ms | 11604 KB | Output is correct |
36 | Correct | 6 ms | 11604 KB | Output is correct |
37 | Correct | 7 ms | 11604 KB | Output is correct |
38 | Correct | 6 ms | 11600 KB | Output is correct |
39 | Correct | 7 ms | 11604 KB | Output is correct |
40 | Correct | 7 ms | 11604 KB | Output is correct |
41 | Correct | 297 ms | 54016 KB | Output is correct |
42 | Correct | 382 ms | 33616 KB | Output is correct |
43 | Correct | 111 ms | 33780 KB | Output is correct |
44 | Correct | 84 ms | 33532 KB | Output is correct |
45 | Correct | 82 ms | 33404 KB | Output is correct |
46 | Correct | 545 ms | 56248 KB | Output is correct |
47 | Correct | 189 ms | 55812 KB | Output is correct |
48 | Correct | 176 ms | 55776 KB | Output is correct |
49 | Correct | 181 ms | 55792 KB | Output is correct |
50 | Correct | 232 ms | 33256 KB | Output is correct |
51 | Correct | 132 ms | 32736 KB | Output is correct |
52 | Correct | 84 ms | 32620 KB | Output is correct |
53 | Correct | 598 ms | 55120 KB | Output is correct |
54 | Correct | 200 ms | 54020 KB | Output is correct |
55 | Correct | 139 ms | 54088 KB | Output is correct |
56 | Correct | 9 ms | 11884 KB | Output is correct |
57 | Correct | 18 ms | 17156 KB | Output is correct |
58 | Correct | 76 ms | 38864 KB | Output is correct |
59 | Correct | 206 ms | 60324 KB | Output is correct |
60 | Correct | 371 ms | 56440 KB | Output is correct |
61 | Correct | 187 ms | 54728 KB | Output is correct |