#include <bits/stdc++.h>
#define int long long
using namespace std;
int timer = 0;
int start[200001];
int en[200001];
vector<int> adj[200001];
void dfs(int i){
start[i] = ++timer;
for(auto j:adj[i])dfs(j);
en[i] = timer;
}
int bit[200001];int n;
void add(int x,int v){
while(x<=n){
bit[x]+=v;
x+=(x&-x);
}
}
int sum(int x){
int su = 0;
while(x>=1){
su+=bit[x];
x-=(x&-x);
}
return su;
}
signed main() {
int m,q;
cin>>n>>m>>q;
vector<int> r[m+1];
int x;cin>>x;
r[x].push_back(1);
for(int i = 2;i<=n;i++){
int pr,x;cin>>pr>>x;
adj[pr].push_back(i);
r[x].push_back(i);
}
dfs(1);
vector<vector<int>> ans,ans2;
int id = -1;int b= 800;
int ge[m+1];
vector<int> noob;
for(int i = 1;i<=m;i++)ge[i] = -1;
for(int i = 1;i<=m;i++){
if(r[i].size()>=b){
noob.push_back(i);
ge[i] = ++id;
for(auto j:r[i]){
add(start[j],1);
}
ans.push_back({});
for(int j = 1;j<=m;j++){
int val = 0;
for(auto k:r[j]){
val+=sum(en[k])-sum(start[k]-1);
}
ans.back().push_back(val);
}
for(auto j:r[i]){
add(start[j],-1);
}
}
}
for(int i = 1;i<=m;i++){
for(auto j:r[i]){
add(start[j],1);
}
ans2.push_back({});
for(auto j:noob){
int val = 0;
for(auto k:r[j]){
val+=sum(en[k])-sum(start[k]-1);
}
ans2.back().push_back(val);
}
for(auto j:r[i]){
add(start[j],-1);
}
}
while(q--){
int a,b;cin>>a>>b;
if(ge[b]!=-1)cout<<ans[ge[b]][a-1]<<"\n";
else if(ge[a]!=-1)cout<<ans2[b-1][ge[a]]<<"\n";
else{
for(auto j:r[b]){
add(start[j],1);
}
int val = 0;
for(auto j:r[a]){
val+=sum(en[j])-sum(start[j]-1);
}
for(auto j:r[b]){
add(start[j],-1);
}
cout<<val<<endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
47 | if(r[i].size()>=b){
| ~~~~~~~~~~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4916 KB |
Output is correct |
3 |
Correct |
5 ms |
4944 KB |
Output is correct |
4 |
Correct |
7 ms |
4944 KB |
Output is correct |
5 |
Correct |
11 ms |
4944 KB |
Output is correct |
6 |
Correct |
23 ms |
5072 KB |
Output is correct |
7 |
Correct |
20 ms |
5072 KB |
Output is correct |
8 |
Correct |
38 ms |
5072 KB |
Output is correct |
9 |
Correct |
58 ms |
5456 KB |
Output is correct |
10 |
Correct |
87 ms |
5584 KB |
Output is correct |
11 |
Correct |
167 ms |
5968 KB |
Output is correct |
12 |
Correct |
179 ms |
6480 KB |
Output is correct |
13 |
Correct |
248 ms |
6364 KB |
Output is correct |
14 |
Correct |
307 ms |
6864 KB |
Output is correct |
15 |
Correct |
483 ms |
8756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1958 ms |
10168 KB |
Output is correct |
2 |
Correct |
2468 ms |
9528 KB |
Output is correct |
3 |
Correct |
3565 ms |
11860 KB |
Output is correct |
4 |
Correct |
458 ms |
7216 KB |
Output is correct |
5 |
Correct |
566 ms |
8456 KB |
Output is correct |
6 |
Correct |
1773 ms |
8728 KB |
Output is correct |
7 |
Correct |
3144 ms |
10156 KB |
Output is correct |
8 |
Correct |
3224 ms |
14048 KB |
Output is correct |
9 |
Correct |
5018 ms |
16364 KB |
Output is correct |
10 |
Correct |
7928 ms |
20220 KB |
Output is correct |
11 |
Execution timed out |
8006 ms |
17940 KB |
Time limit exceeded |
12 |
Execution timed out |
8089 ms |
18648 KB |
Time limit exceeded |
13 |
Execution timed out |
8035 ms |
18464 KB |
Time limit exceeded |
14 |
Execution timed out |
8064 ms |
21220 KB |
Time limit exceeded |
15 |
Execution timed out |
8022 ms |
21632 KB |
Time limit exceeded |
16 |
Execution timed out |
8089 ms |
24584 KB |
Time limit exceeded |
17 |
Execution timed out |
8018 ms |
26280 KB |
Time limit exceeded |