| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 669949 |
2022-12-07T16:29:01 Z |
Iliya |
Regions (IOI09_regions) |
C++17 |
|
5087 ms |
81256 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 r2, int r1){
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 |
Incorrect |
5 ms |
8400 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
8400 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
8400 KB |
Output isn't correct |
| 4 |
Incorrect |
8 ms |
8400 KB |
Output isn't correct |
| 5 |
Incorrect |
11 ms |
8400 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
8912 KB |
Output isn't correct |
| 7 |
Incorrect |
30 ms |
8784 KB |
Output isn't correct |
| 8 |
Incorrect |
31 ms |
8912 KB |
Output isn't correct |
| 9 |
Incorrect |
48 ms |
9636 KB |
Output isn't correct |
| 10 |
Incorrect |
101 ms |
9680 KB |
Output isn't correct |
| 11 |
Incorrect |
126 ms |
9808 KB |
Output isn't correct |
| 12 |
Incorrect |
142 ms |
10704 KB |
Output isn't correct |
| 13 |
Incorrect |
201 ms |
10064 KB |
Output isn't correct |
| 14 |
Incorrect |
237 ms |
10512 KB |
Output isn't correct |
| 15 |
Incorrect |
277 ms |
14436 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1861 ms |
14156 KB |
Output isn't correct |
| 2 |
Incorrect |
2256 ms |
12656 KB |
Output isn't correct |
| 3 |
Incorrect |
2672 ms |
16772 KB |
Output isn't correct |
| 4 |
Incorrect |
294 ms |
17488 KB |
Output isn't correct |
| 5 |
Incorrect |
450 ms |
21760 KB |
Output isn't correct |
| 6 |
Incorrect |
621 ms |
24560 KB |
Output isn't correct |
| 7 |
Incorrect |
1591 ms |
31048 KB |
Output isn't correct |
| 8 |
Incorrect |
1290 ms |
38224 KB |
Output isn't correct |
| 9 |
Incorrect |
2790 ms |
46444 KB |
Output isn't correct |
| 10 |
Incorrect |
4342 ms |
71964 KB |
Output isn't correct |
| 11 |
Incorrect |
5087 ms |
64268 KB |
Output isn't correct |
| 12 |
Incorrect |
2189 ms |
49200 KB |
Output isn't correct |
| 13 |
Incorrect |
2406 ms |
49876 KB |
Output isn't correct |
| 14 |
Incorrect |
2387 ms |
56756 KB |
Output isn't correct |
| 15 |
Incorrect |
4008 ms |
72232 KB |
Output isn't correct |
| 16 |
Incorrect |
3319 ms |
81256 KB |
Output isn't correct |
| 17 |
Incorrect |
2846 ms |
70196 KB |
Output isn't correct |
