#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#pragma GCC optimize(2)
#define l int
int read(){
char x = getchar();
int val = 0;
while(x<'0'||x>'9')x=getchar();
while('0'<=x&&x<='9')
val = val*10+x-'0', x=getchar();
return val;
}
void print(int num){
if(num<0){
putchar('-');
num*=-1;
}
if(num>9) {
print(num/10);
}
putchar((num%10)^48);
}
using namespace std;
vector<l> adj[200001];
vector<pair<l,l>> arr[25001];
l region[200001], t, in[200001], out[200001], li[200001], sz[25001], lg[401];
gp_hash_table<int,int> ans1[401];
gp_hash_table<int,array<int,401>> ans2;
void merge(gp_hash_table<l, l> &a, gp_hash_table<l, l> b){
if(a.size()<b.size())
swap(a, b);
for(auto i: b)
a[i.first]+=i.second;
}
gp_hash_table<l,l> dfs(l n){
gp_hash_table<l,l> cur;
cur[region[n]]=1;
in[n]=t++;
arr[region[n]].push_back({in[n],1});
for(auto i: adj[n]){
merge(cur, dfs(i));
}
out[n]=t++;
arr[region[n]].push_back({out[n],0});
if(li[region[n]])
for(auto i: cur)
ans1[li[region[n]]][i.first]+=i.second;
else
for(auto i: lg)
ans2[region[n]][li[i]]+=cur[i];
return cur;
}
l query_s(int r1, int r2){
l sum=0, o=0, a=0, b=0;
vector<int> v;
while(a<arr[r1].size()||b<arr[r2].size()){
if(a<arr[r1].size()&&b<arr[r2].size()){
if(arr[r1][a]<arr[r2][b])
v.push_back(arr[r1][a].second*2-1), a++;
else
v.push_back(0), b++;
} else if(a<arr[r1].size())
v.push_back(arr[r1][a].second*2-1), a++;
else
v.push_back(0), b++;
}
for(auto i: v)
if(i)
o+=i;
else
sum+=o;
return sum/2;
}
int main(){
l n=read(), r=read(), q=read(), lr=0;
region[1]=read();
for(l i = 2; i <= n; i++){
adj[read()].push_back(i);
region[i] = read();
sz[region[i]]++;
}
for(int i = 1; i <= r; i++)
if(sz[i]>500)
lg[lr]=i, li[i]=++lr;
dfs(1);
while(q--){
int r1=read(), r2=read();
if(li[r1])
print(ans1[li[r1]][r2]);
else if(li[r2])
print(ans2[r1][li[r2]]);
else
print(query_s(r1, r2));
puts("");
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp: In function 'int query_s(int, int)':
regions.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | while(a<arr[r1].size()||b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | while(a<arr[r1].size()||b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(a<arr[r1].size()&&b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(a<arr[r1].size()&&b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | } else if(a<arr[r1].size())
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8952 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9104 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9304 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9304 KB |
Output is correct |
| 6 |
Correct |
14 ms |
10508 KB |
Output is correct |
| 7 |
Correct |
17 ms |
10196 KB |
Output is correct |
| 8 |
Correct |
25 ms |
10332 KB |
Output is correct |
| 9 |
Correct |
56 ms |
13000 KB |
Output is correct |
| 10 |
Correct |
79 ms |
11948 KB |
Output is correct |
| 11 |
Correct |
111 ms |
12384 KB |
Output is correct |
| 12 |
Correct |
182 ms |
13328 KB |
Output is correct |
| 13 |
Correct |
166 ms |
12536 KB |
Output is correct |
| 14 |
Correct |
235 ms |
11980 KB |
Output is correct |
| 15 |
Correct |
395 ms |
24132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
948 ms |
18368 KB |
Output is correct |
| 2 |
Correct |
888 ms |
14028 KB |
Output is correct |
| 3 |
Correct |
1844 ms |
24184 KB |
Output is correct |
| 4 |
Correct |
329 ms |
30364 KB |
Output is correct |
| 5 |
Correct |
1188 ms |
37420 KB |
Output is correct |
| 6 |
Correct |
1160 ms |
51828 KB |
Output is correct |
| 7 |
Correct |
1731 ms |
91464 KB |
Output is correct |
| 8 |
Correct |
7303 ms |
112232 KB |
Output is correct |
| 9 |
Correct |
5269 ms |
100744 KB |
Output is correct |
| 10 |
Execution timed out |
8021 ms |
117792 KB |
Time limit exceeded |
| 11 |
Runtime error |
598 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Correct |
2037 ms |
99104 KB |
Output is correct |
| 13 |
Correct |
5522 ms |
102632 KB |
Output is correct |
| 14 |
Runtime error |
1236 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Execution timed out |
8026 ms |
115944 KB |
Time limit exceeded |
| 16 |
Runtime error |
3695 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
3493 ms |
131072 KB |
Execution killed with signal 9 |
