# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
415187 | 2021-05-31T16:21:05 Z | Alex_tz307 | Regions (IOI09_regions) | C++17 | 8000 ms | 35524 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5; const int MAXR = 25 * 1e3; int r[MAXN], timer, in[MAXN], out[MAXN]; vector<int> G[MAXN], R[MAXR], pos[MAXR]; void dfs(int u) { in[u] = ++timer; pos[r[u]].emplace_back(in[u]); for (int v : G[u]) dfs(v); out[u] = timer; } int solve(int r1, int r2) { int ans = 0; for (int u : R[r1]) { int n = pos[r2].size(); int st = n, dr = n, l = 0, r = n - 1; while (l <= r) { int mid = (l + r) >> 1; if (in[u] <= pos[r2][mid]) { st = mid; r = mid - 1; } else l = mid + 1; } l = 0, r = n - 1; while (l <= r) { int mid = (l + r) >> 1; if (out[u] < pos[r2][mid]) { dr = mid; r = mid - 1; } else l = mid + 1; } ans += dr - st; } return ans; } int main() { int n, Q; scanf("%d %d %d", &n, &Q, &Q); for (int v = 0; v < n; ++v) { if (v == 0) { scanf("%d", &r[0]); --r[0]; R[r[0]].emplace_back(0); continue; } int u; scanf("%d %d", &u, &r[v]); --r[v]; G[u - 1].emplace_back(v); R[r[v]].emplace_back(v); } dfs(0); map<pair<int,int>,int> sol; for (int q = 0; q < Q; ++q) { int r1, r2; scanf("%d %d", &r1, &r2); --r1, --r2; pair<int,int> p{r1, r2}; auto it = sol.find(p); if (it != sol.end()) { printf("%d\n", it->second); fflush(stdout); } else { int ans = solve(r1, r2); sol[p] = ans; printf("%d\n", ans); fflush(stdout); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 6088 KB | Output is correct |
2 | Correct | 4 ms | 6088 KB | Output is correct |
3 | Correct | 6 ms | 6088 KB | Output is correct |
4 | Correct | 8 ms | 6088 KB | Output is correct |
5 | Correct | 12 ms | 6216 KB | Output is correct |
6 | Correct | 24 ms | 6324 KB | Output is correct |
7 | Correct | 38 ms | 6336 KB | Output is correct |
8 | Correct | 39 ms | 6464 KB | Output is correct |
9 | Correct | 53 ms | 6772 KB | Output is correct |
10 | Correct | 104 ms | 7108 KB | Output is correct |
11 | Correct | 134 ms | 7532 KB | Output is correct |
12 | Correct | 172 ms | 8112 KB | Output is correct |
13 | Correct | 242 ms | 7968 KB | Output is correct |
14 | Correct | 340 ms | 8432 KB | Output is correct |
15 | Correct | 329 ms | 10580 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1643 ms | 12204 KB | Output is correct |
2 | Correct | 1939 ms | 11276 KB | Output is correct |
3 | Correct | 2531 ms | 15948 KB | Output is correct |
4 | Correct | 382 ms | 9400 KB | Output is correct |
5 | Correct | 543 ms | 11144 KB | Output is correct |
6 | Correct | 702 ms | 11020 KB | Output is correct |
7 | Correct | 1236 ms | 11464 KB | Output is correct |
8 | Correct | 1339 ms | 18124 KB | Output is correct |
9 | Correct | 2868 ms | 23440 KB | Output is correct |
10 | Correct | 4895 ms | 29280 KB | Output is correct |
11 | Correct | 5383 ms | 27376 KB | Output is correct |
12 | Correct | 5749 ms | 21896 KB | Output is correct |
13 | Correct | 6632 ms | 23920 KB | Output is correct |
14 | Execution timed out | 8016 ms | 24184 KB | Time limit exceeded |
15 | Execution timed out | 8029 ms | 29956 KB | Time limit exceeded |
16 | Execution timed out | 8087 ms | 35524 KB | Time limit exceeded |
17 | Correct | 7141 ms | 34032 KB | Output is correct |