# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
440158 |
2021-07-01T16:31:08 Z |
dutch |
Regions (IOI09_regions) |
C++17 |
|
5576 ms |
31864 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 450;
int k[MAXN], cnt[MAXK], t[MAXN], s[MAXN], dfsTimer = 0, cur, c;
vector<int> g[MAXN], a[MAXN], res[MAXK], ord[MAXK];
void dfs0(int u){
t[u] = dfsTimer++, s[u] = 1;
ord[k[u]].push_back(t[u]);
for(int v : g[u]) dfs0(v), s[u] += s[v];
}
void dfs1(int u){
if(k[u] == cur) ++c;
res[cur][k[u]] += c;
for(int v : g[u]) dfs1(v);
if(k[u] == cur) --c;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, r, q, x, y; cin >> n >> r >> q;
for(int i=0, j; i<n; ++i){
if(i) cin >> j, g[j-1].push_back(i);
cin >> k[i], a[--k[i]].push_back(i);
}
dfs0(0);
for(int i=0; i<r; ++i){
if(a[i].size() < SQRT) continue;
cur = i, c = 0;
res[i].resize(r);
dfs1(0);
}
while(q--){
cin >> x >> y; --x, --y;
if(a[x].size() < SQRT){
int ans = 0;
for(int u : a[x]){
ans += upper_bound(ord[y].begin(), ord[y].end(), t[u]+s[u]-1)
- lower_bound(ord[y].begin(), ord[y].end(), t[u]);
}
cout << ans << endl;
}else{
cout << res[x][y] << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
10824 KB |
Output is correct |
2 |
Correct |
9 ms |
10824 KB |
Output is correct |
3 |
Correct |
10 ms |
10824 KB |
Output is correct |
4 |
Correct |
14 ms |
10824 KB |
Output is correct |
5 |
Correct |
17 ms |
10824 KB |
Output is correct |
6 |
Correct |
30 ms |
10936 KB |
Output is correct |
7 |
Correct |
35 ms |
10956 KB |
Output is correct |
8 |
Correct |
45 ms |
11008 KB |
Output is correct |
9 |
Correct |
56 ms |
11336 KB |
Output is correct |
10 |
Correct |
101 ms |
11336 KB |
Output is correct |
11 |
Correct |
139 ms |
11624 KB |
Output is correct |
12 |
Correct |
222 ms |
12232 KB |
Output is correct |
13 |
Correct |
241 ms |
11848 KB |
Output is correct |
14 |
Correct |
402 ms |
12464 KB |
Output is correct |
15 |
Correct |
383 ms |
15048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2542 ms |
15512 KB |
Output is correct |
2 |
Correct |
2764 ms |
14364 KB |
Output is correct |
3 |
Correct |
3666 ms |
17216 KB |
Output is correct |
4 |
Correct |
407 ms |
12488 KB |
Output is correct |
5 |
Correct |
405 ms |
14176 KB |
Output is correct |
6 |
Correct |
591 ms |
15436 KB |
Output is correct |
7 |
Correct |
2131 ms |
15392 KB |
Output is correct |
8 |
Correct |
1537 ms |
23756 KB |
Output is correct |
9 |
Correct |
3175 ms |
20292 KB |
Output is correct |
10 |
Correct |
4715 ms |
30552 KB |
Output is correct |
11 |
Correct |
5576 ms |
20176 KB |
Output is correct |
12 |
Correct |
1738 ms |
21672 KB |
Output is correct |
13 |
Correct |
2762 ms |
21868 KB |
Output is correct |
14 |
Correct |
3320 ms |
23320 KB |
Output is correct |
15 |
Correct |
3981 ms |
26080 KB |
Output is correct |
16 |
Correct |
4091 ms |
31464 KB |
Output is correct |
17 |
Correct |
3759 ms |
31864 KB |
Output is correct |