| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 669873 |
2022-12-07T14:49:58 Z |
Iliya |
Regions (IOI09_regions) |
C++17 |
|
5681 ms |
81236 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 = 469;
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]]]--;
}
int solve(int r1, int r2){
if((int) Home[r1].size() >= SQ) return !(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;
}
return !(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 |
8400 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8400 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8400 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8400 KB |
Output is correct |
| 5 |
Correct |
10 ms |
8400 KB |
Output is correct |
| 6 |
Correct |
19 ms |
8912 KB |
Output is correct |
| 7 |
Correct |
31 ms |
8784 KB |
Output is correct |
| 8 |
Correct |
32 ms |
8912 KB |
Output is correct |
| 9 |
Correct |
27 ms |
9552 KB |
Output is correct |
| 10 |
Correct |
90 ms |
9680 KB |
Output is correct |
| 11 |
Correct |
131 ms |
9808 KB |
Output is correct |
| 12 |
Correct |
148 ms |
10704 KB |
Output is correct |
| 13 |
Correct |
197 ms |
10064 KB |
Output is correct |
| 14 |
Correct |
288 ms |
10520 KB |
Output is correct |
| 15 |
Correct |
273 ms |
14412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1929 ms |
14156 KB |
Output isn't correct |
| 2 |
Incorrect |
2237 ms |
12660 KB |
Output isn't correct |
| 3 |
Incorrect |
3090 ms |
16772 KB |
Output isn't correct |
| 4 |
Correct |
404 ms |
17488 KB |
Output is correct |
| 5 |
Correct |
515 ms |
21704 KB |
Output is correct |
| 6 |
Incorrect |
718 ms |
24516 KB |
Output isn't correct |
| 7 |
Incorrect |
2231 ms |
31104 KB |
Output isn't correct |
| 8 |
Incorrect |
1383 ms |
38300 KB |
Output isn't correct |
| 9 |
Correct |
2994 ms |
46440 KB |
Output is correct |
| 10 |
Incorrect |
5110 ms |
71956 KB |
Output isn't correct |
| 11 |
Correct |
5681 ms |
64332 KB |
Output is correct |
| 12 |
Incorrect |
2169 ms |
49188 KB |
Output isn't correct |
| 13 |
Incorrect |
2636 ms |
49872 KB |
Output isn't correct |
| 14 |
Incorrect |
3028 ms |
56756 KB |
Output isn't correct |
| 15 |
Incorrect |
4089 ms |
72264 KB |
Output isn't correct |
| 16 |
Incorrect |
3576 ms |
81236 KB |
Output isn't correct |
| 17 |
Incorrect |
3864 ms |
70180 KB |
Output isn't correct |
