# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
53639 | 2018-06-30T15:28:18 Z | baactree | Regions (IOI09_regions) | C++17 | 6170 ms | 131072 KB |
#include <bits/stdc++.h> using namespace std; int n, r, q; vector<int> adj[200005]; int arr[200005]; const int sz = 2000; int cache[sz][25005]; pair<int, int> cnt[25005]; int inv[25005]; int le[200005], ri[200005]; vector<int> lv[25005], rv[25005]; vector<int> vec[25005]; int vn; void dfs(int now, int par) { vec[arr[now]].push_back(now); le[now] = vn++; lv[arr[now]].push_back(le[now]); for (auto &there : adj[now]) { if (there == par)continue; dfs(there, now); } ri[now] = vn++; rv[arr[now]].push_back(ri[now]); } int main() { scanf("%d%d%d", &n, &r, &q); scanf("%d", &arr[1]); cnt[arr[1]].first++; for (int i = 2; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(i); adj[i].push_back(a); arr[i] = b; cnt[arr[i]].first++; } for (int i = 0; i < 25005; i++) cnt[i].second = i; sort(cnt, cnt + 25005, [&](pair<int, int> &a, pair<int, int> &b) { return a > b; }); for (int i = 0; i < 25005; i++) inv[cnt[i].second] = i; dfs(1, 0); memset(cache, -1, sizeof(cache)); while (q--) { int a, b; scanf("%d%d", &a, &b); if (inv[b] < sz) { int &ans = cache[inv[b]][a]; if (ans == -1) { ans = 0; for (auto x : vec[b]) ans += (lower_bound(lv[a].begin(), lv[a].end(), le[x]) - lv[a].begin()) - (lower_bound(rv[a].begin(), rv[a].end(), le[x]) - rv[a].begin()); } printf("%d\n", ans); fflush(stdout); } else { int ans = 0; for (auto x : vec[b]) ans += (lower_bound(lv[a].begin(), lv[a].end(), le[x]) - lv[a].begin()) - (lower_bound(rv[a].begin(), rv[a].end(), le[x]) - rv[a].begin()); printf("%d\n", ans); fflush(stdout); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 330 ms | 131072 KB | Output is correct |
2 | Correct | 281 ms | 131072 KB | Output is correct |
3 | Correct | 279 ms | 131072 KB | Output is correct |
4 | Correct | 294 ms | 131072 KB | Output is correct |
5 | Correct | 312 ms | 131072 KB | Output is correct |
6 | Correct | 321 ms | 131072 KB | Output is correct |
7 | Correct | 314 ms | 131072 KB | Output is correct |
8 | Correct | 311 ms | 131072 KB | Output is correct |
9 | Correct | 345 ms | 131072 KB | Output is correct |
10 | Correct | 445 ms | 131072 KB | Output is correct |
11 | Correct | 398 ms | 131072 KB | Output is correct |
12 | Correct | 459 ms | 131072 KB | Output is correct |
13 | Correct | 595 ms | 131072 KB | Output is correct |
14 | Correct | 690 ms | 131072 KB | Output is correct |
15 | Correct | 601 ms | 131072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2105 ms | 131072 KB | Output is correct |
2 | Correct | 2277 ms | 131072 KB | Output is correct |
3 | Correct | 3118 ms | 131072 KB | Output is correct |
4 | Correct | 781 ms | 131072 KB | Output is correct |
5 | Correct | 847 ms | 131072 KB | Output is correct |
6 | Correct | 1034 ms | 131072 KB | Output is correct |
7 | Correct | 1232 ms | 131072 KB | Output is correct |
8 | Correct | 1975 ms | 131072 KB | Output is correct |
9 | Correct | 4016 ms | 131072 KB | Output is correct |
10 | Execution timed out | 4266 ms | 131072 KB | Time limit exceeded (wall clock) |
11 | Execution timed out | 5317 ms | 131072 KB | Time limit exceeded (wall clock) |
12 | Execution timed out | 6170 ms | 131072 KB | Time limit exceeded (wall clock) |
13 | Execution timed out | 5715 ms | 131072 KB | Time limit exceeded (wall clock) |
14 | Execution timed out | 5349 ms | 131072 KB | Time limit exceeded (wall clock) |
15 | Execution timed out | 4593 ms | 131072 KB | Time limit exceeded (wall clock) |
16 | Execution timed out | 5058 ms | 131072 KB | Time limit exceeded (wall clock) |
17 | Execution timed out | 4981 ms | 131072 KB | Time limit exceeded (wall clock) |