# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
199610 | 2020-02-02T08:38:15 Z | songc | Regions (IOI09_regions) | C++14 | 102 ms | 26360 KB |
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; int N, num, Q; int qa[202020], qb[202020], C[202020], sz[202020], P[202020]; vector<int> S[202020], U[202020]; vector<int> adj[202020], cnt[202020]; map<pii,LL> ans; void dfs(int u){ int x=++num, a=C[u]; cnt[a].push_back(x), P[a]++; for (int v : adj[u]) dfs(v); sort(S[a].begin(), S[a].end()); S[a].erase(unique(S[a].begin(), S[a].end()), S[a].end()); sort(U[a].begin(), U[a].end()); U[a].erase(unique(U[a].begin(), U[a].end()), U[a].end()); for (int b : S[a]) ans[pii(b, a)] += cnt[b].size()-(lower_bound(cnt[b].begin(), cnt[b].end(), x)-cnt[b].begin()); for (int b : U[a]) ans[pii(a, b)] += P[b]; P[a]--; } int main(){ scanf("%d %*d %d", &N, &Q); scanf("%d", &C[1]); for (int i=2; i<=N; i++){ int p; scanf("%d %d", &p, &C[i]); adj[p].push_back(i); sz[C[i]]++; } for (int i=1; i<=Q; i++){ scanf("%d %d", &qb[i], &qa[i]); if (sz[qa[i]] < sz[qb[i]]) U[qa[i]].push_back(qb[i]); else S[qb[i]].push_back(qa[i]); } dfs(1); for (int i=1; i<=Q; i++) printf("%lld\n", ans[pii(qa[i], qb[i])]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 15 ms | 19192 KB | Time limit exceeded (wall clock) |
2 | Execution timed out | 15 ms | 19192 KB | Time limit exceeded (wall clock) |
3 | Execution timed out | 15 ms | 19320 KB | Time limit exceeded (wall clock) |
4 | Execution timed out | 15 ms | 19320 KB | Time limit exceeded (wall clock) |
5 | Execution timed out | 16 ms | 19320 KB | Time limit exceeded (wall clock) |
6 | Execution timed out | 15 ms | 19320 KB | Time limit exceeded (wall clock) |
7 | Execution timed out | 16 ms | 19320 KB | Time limit exceeded (wall clock) |
8 | Execution timed out | 17 ms | 19396 KB | Time limit exceeded (wall clock) |
9 | Execution timed out | 17 ms | 19448 KB | Time limit exceeded (wall clock) |
10 | Execution timed out | 19 ms | 19576 KB | Time limit exceeded (wall clock) |
11 | Execution timed out | 21 ms | 19704 KB | Time limit exceeded (wall clock) |
12 | Execution timed out | 22 ms | 19960 KB | Time limit exceeded (wall clock) |
13 | Execution timed out | 25 ms | 19704 KB | Time limit exceeded (wall clock) |
14 | Execution timed out | 27 ms | 20216 KB | Time limit exceeded (wall clock) |
15 | Execution timed out | 27 ms | 20600 KB | Time limit exceeded (wall clock) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 46 ms | 21752 KB | Time limit exceeded (wall clock) |
2 | Execution timed out | 41 ms | 21112 KB | Time limit exceeded (wall clock) |
3 | Execution timed out | 43 ms | 22392 KB | Time limit exceeded (wall clock) |
4 | Execution timed out | 27 ms | 20216 KB | Time limit exceeded (wall clock) |
5 | Execution timed out | 26 ms | 20600 KB | Time limit exceeded (wall clock) |
6 | Execution timed out | 33 ms | 20856 KB | Time limit exceeded (wall clock) |
7 | Execution timed out | 39 ms | 21372 KB | Time limit exceeded (wall clock) |
8 | Execution timed out | 51 ms | 22776 KB | Time limit exceeded (wall clock) |
9 | Execution timed out | 66 ms | 24184 KB | Time limit exceeded (wall clock) |
10 | Execution timed out | 76 ms | 25288 KB | Time limit exceeded (wall clock) |
11 | Execution timed out | 102 ms | 23800 KB | Time limit exceeded (wall clock) |
12 | Execution timed out | 84 ms | 25900 KB | Time limit exceeded (wall clock) |
13 | Execution timed out | 85 ms | 25336 KB | Time limit exceeded (wall clock) |
14 | Execution timed out | 96 ms | 25208 KB | Time limit exceeded (wall clock) |
15 | Execution timed out | 87 ms | 26360 KB | Time limit exceeded (wall clock) |
16 | Execution timed out | 85 ms | 26360 KB | Time limit exceeded (wall clock) |
17 | Execution timed out | 85 ms | 26324 KB | Time limit exceeded (wall clock) |