# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
351595 | 2021-01-20T05:48:19 Z | Noran | File Paths (BOI15_fil) | C++14 | 313 ms | 5612 KB |
#include <bits/stdc++.h> #define SZ(AA) int((AA).size()) using namespace std; const int MAXN = 6000, MAXK = 1000000; vector<int> ve[MAXN + 10]; int N, M, K, S, h[MAXN + 10], cnt[MAXK + 10]; bool res[MAXN + 10], us[MAXK + 10]; void add(int v, int delta, int x) { if (v > N) { return; } int y = h[v] + delta; if (y <= MAXK) { cnt[y] += x; } for (int w : ve[v]) { add(w, delta, x); } } // use cycle void case1(int v) { if (v > N) { int y = K - h[v]; if (y > 0) { for (int d = 1; d * d <= y; ++d) { if (y % d == 0 && (cnt[d] > 0 || cnt[y / d] > 0)) { res[v] = true; } } } return; } add(v, S + 1 - h[v], 1); for (int w : ve[v]) { case1(w); } add(v, S + 1 - h[v], -1); } vector<int> anc; // use single directory symlink void case2(int v) { if (v > N) { for (int a : anc) { int y = K - (h[v] - h[a]) - (S + 1); if (y >= 0 && us[y]) { res[v] = true; } } return; } anc.push_back(v); for (int w : ve[v]) { case2(w); } anc.pop_back(); } // do not use symlinks at all void case3() { for (int i = N + 1; i <= N + M; ++i) { if (h[i] == K) { res[i] = true; } } } // use file symlink void case4() { for (int i = 0; i <= N; ++i) { if (h[i] + S == K) { for (int j = N + 1; j <= N + M; ++j) { res[j] = true; } return; } } } int main(void) { scanf("%d%d%d%d", &N, &M, &K, &S); h[0] = 1; us[1] = true; for (int i = 1; i <= N + M; ++i) { int p; scanf("%d%d", &p, &h[i]); ve[p].push_back(i); h[i] += h[p] + (i <= N ? 1 : 0); if (i <= N) { us[h[i]] = true; } } case1(0); case2(0); case3(); //case4(); for (int i = N + 1; i <= N + M; ++i) { puts(res[i] ? "YES" : "NO"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 2 ms | 1004 KB | Output is correct |
4 | Correct | 4 ms | 1004 KB | Output is correct |
5 | Correct | 8 ms | 4716 KB | Output is correct |
6 | Correct | 5 ms | 3308 KB | Output is correct |
7 | Correct | 11 ms | 4588 KB | Output is correct |
8 | Correct | 5 ms | 4332 KB | Output is correct |
9 | Correct | 5 ms | 4460 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
12 | Correct | 4 ms | 876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 5228 KB | Output is correct |
2 | Correct | 13 ms | 5100 KB | Output is correct |
3 | Correct | 12 ms | 5356 KB | Output is correct |
4 | Correct | 12 ms | 5356 KB | Output is correct |
5 | Correct | 225 ms | 5356 KB | Output is correct |
6 | Correct | 191 ms | 5612 KB | Output is correct |
7 | Correct | 122 ms | 5228 KB | Output is correct |
8 | Correct | 113 ms | 5484 KB | Output is correct |
9 | Correct | 13 ms | 4844 KB | Output is correct |
10 | Correct | 13 ms | 4332 KB | Output is correct |
11 | Correct | 7 ms | 748 KB | Output is correct |
12 | Correct | 176 ms | 2540 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 2 ms | 1004 KB | Output is correct |
4 | Correct | 4 ms | 1004 KB | Output is correct |
5 | Correct | 8 ms | 4716 KB | Output is correct |
6 | Correct | 5 ms | 3308 KB | Output is correct |
7 | Correct | 11 ms | 4588 KB | Output is correct |
8 | Correct | 5 ms | 4332 KB | Output is correct |
9 | Correct | 5 ms | 4460 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
12 | Correct | 4 ms | 876 KB | Output is correct |
13 | Correct | 13 ms | 5228 KB | Output is correct |
14 | Correct | 13 ms | 5100 KB | Output is correct |
15 | Correct | 12 ms | 5356 KB | Output is correct |
16 | Correct | 12 ms | 5356 KB | Output is correct |
17 | Correct | 225 ms | 5356 KB | Output is correct |
18 | Correct | 191 ms | 5612 KB | Output is correct |
19 | Correct | 122 ms | 5228 KB | Output is correct |
20 | Correct | 113 ms | 5484 KB | Output is correct |
21 | Correct | 13 ms | 4844 KB | Output is correct |
22 | Correct | 13 ms | 4332 KB | Output is correct |
23 | Correct | 7 ms | 748 KB | Output is correct |
24 | Correct | 176 ms | 2540 KB | Output is correct |
25 | Correct | 12 ms | 4972 KB | Output is correct |
26 | Correct | 12 ms | 5228 KB | Output is correct |
27 | Correct | 12 ms | 5356 KB | Output is correct |
28 | Correct | 15 ms | 5356 KB | Output is correct |
29 | Correct | 313 ms | 5484 KB | Output is correct |
30 | Correct | 251 ms | 5340 KB | Output is correct |
31 | Correct | 136 ms | 5356 KB | Output is correct |
32 | Correct | 172 ms | 5228 KB | Output is correct |
33 | Correct | 10 ms | 4204 KB | Output is correct |
34 | Correct | 9 ms | 4332 KB | Output is correct |
35 | Correct | 7 ms | 748 KB | Output is correct |
36 | Correct | 210 ms | 1644 KB | Output is correct |