| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 669999 |
2022-12-07T17:55:09 Z |
Iliya |
Regions (IOI09_regions) |
C++17 |
|
5426 ms |
84272 KB |
/*
Lemme check my list of powers and weaknesses:
ability to do anything, but only whenever I want.
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, R = 3e4, Q = 2e5 + 10, SQ = 499;
int n, r, q, Time, H[N], P[N], St[N], Ft[N], ID[R], cnt[N], Ans[SQ][R];
vector<int> Adj[N], Reg[R], Home[R];
void PreDFS(int v){
St[v] = ++Time;
Reg[H[v]].push_back(Time);
for(int u : Adj[v])
PreDFS(u);
Ft[v] = Time;
}
void DFS(int v){
if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]++;
for(int u : Adj[v]){
for(int i = 1; i < SQ; i++)
Ans[i][H[u]] += cnt[i];
DFS(u);
}
if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]--;
}
void solve(int r1, int r2){
if((int) Home[r1].size() >= SQ) cout << Ans[ID[r1]][r2] << endl;
else{
int Res = 0;
for(int x : Home[r1]){
auto X1 = lower_bound(Reg[r2].begin(), Reg[r2].end(), St[x]);
auto X2 = upper_bound(Reg[r2].begin(), Reg[r2].end(), Ft[x]);
Res += X2 - X1;
}
cout << Res << endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> r >> q;
for(int i = 1; i <= n; i++){
if(i == 1){
cin >> H[i];
Home[H[i]].push_back(i);
}
else {
cin >> P[i] >> H[i];
Adj[P[i]].push_back(i);
Home[H[i]].push_back(i);
}
}
PreDFS(1);
int ind = 0;
for(int i = 1; i <= r; i++)
if((int) Home[i].size() >= SQ)
ID[i] = ++ind;
DFS(1);
while(q--){
int r1, r2;
cin >> r1 >> r2;
solve(r1, r2);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8528 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8528 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8528 KB |
Output is correct |
| 5 |
Correct |
10 ms |
8656 KB |
Output is correct |
| 6 |
Correct |
23 ms |
9040 KB |
Output is correct |
| 7 |
Correct |
25 ms |
8940 KB |
Output is correct |
| 8 |
Correct |
20 ms |
9040 KB |
Output is correct |
| 9 |
Correct |
46 ms |
9808 KB |
Output is correct |
| 10 |
Correct |
50 ms |
9980 KB |
Output is correct |
| 11 |
Correct |
139 ms |
9964 KB |
Output is correct |
| 12 |
Correct |
161 ms |
10968 KB |
Output is correct |
| 13 |
Correct |
200 ms |
10320 KB |
Output is correct |
| 14 |
Correct |
323 ms |
10676 KB |
Output is correct |
| 15 |
Correct |
261 ms |
14572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1975 ms |
14320 KB |
Output is correct |
| 2 |
Correct |
2092 ms |
12812 KB |
Output is correct |
| 3 |
Correct |
2774 ms |
16936 KB |
Output is correct |
| 4 |
Correct |
339 ms |
18248 KB |
Output is correct |
| 5 |
Correct |
473 ms |
22484 KB |
Output is correct |
| 6 |
Correct |
991 ms |
25472 KB |
Output is correct |
| 7 |
Correct |
1757 ms |
32388 KB |
Output is correct |
| 8 |
Correct |
1534 ms |
39512 KB |
Output is correct |
| 9 |
Correct |
2648 ms |
48396 KB |
Output is correct |
| 10 |
Correct |
4534 ms |
75044 KB |
Output is correct |
| 11 |
Correct |
5426 ms |
67444 KB |
Output is correct |
| 12 |
Correct |
2183 ms |
51264 KB |
Output is correct |
| 13 |
Correct |
2535 ms |
51908 KB |
Output is correct |
| 14 |
Correct |
2925 ms |
59328 KB |
Output is correct |
| 15 |
Correct |
3949 ms |
75264 KB |
Output is correct |
| 16 |
Correct |
3512 ms |
84272 KB |
Output is correct |
| 17 |
Correct |
3416 ms |
72708 KB |
Output is correct |
