#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define l long long
using namespace std;
vector<l> adj[200001], lg;
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[21][25001], ans2[25001][21], in[200001], out[200001], li[200001], sz[25001];
void merge(unordered_map<l, l> &a, unordered_map<l, l> b){
if(a.size()<b.size())
swap(a, b);
for(auto i: b)
a[i.first]+=i.second;
}
unordered_map<l,l> dfs(l n){
unordered_map<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(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
l n, r, q, lr=0;
cin >> n >> r >> q;
cin >> region[1];
for(l i = 2; i <= n; i++){
l p;
cin >> p >> region[i];
sz[region[i]]++;
adj[p].push_back(i);
}
for(int i = 1; i <= r; i++)
if(sz[i]>10000)
lg.push_back(i), li[i]=++lr;
dfs(1);
while(q--){
int r1, r2;
cin >> r1 >> r2;
if(li[r1])
cout << ans1[li[r1]][r2] << endl;
else if(li[r2])
cout << ans2[r1][li[r2]] << endl;
else
cout << query_s(r1, r2) << endl;
}
return 0;
}
Compilation message
regions.cpp: In function 'long long int query_s(int, int)':
regions.cpp:35:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while(a<arr[r1].size()||b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:35:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while(a<arr[r1].size()||b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:36:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(a<arr[r1].size()&&b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:36:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(a<arr[r1].size()&&b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | } else if(a<arr[r1].size())
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5584 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5584 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5584 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5584 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5712 KB |
Output is correct |
| 6 |
Correct |
19 ms |
5840 KB |
Output is correct |
| 7 |
Correct |
29 ms |
5968 KB |
Output is correct |
| 8 |
Correct |
21 ms |
5840 KB |
Output is correct |
| 9 |
Correct |
34 ms |
7376 KB |
Output is correct |
| 10 |
Correct |
57 ms |
6688 KB |
Output is correct |
| 11 |
Correct |
128 ms |
7392 KB |
Output is correct |
| 12 |
Correct |
135 ms |
8784 KB |
Output is correct |
| 13 |
Correct |
174 ms |
8080 KB |
Output is correct |
| 14 |
Correct |
234 ms |
9108 KB |
Output is correct |
| 15 |
Correct |
374 ms |
19976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3396 ms |
16852 KB |
Output is correct |
| 2 |
Correct |
4323 ms |
13476 KB |
Output is correct |
| 3 |
Correct |
3043 ms |
22076 KB |
Output is correct |
| 4 |
Correct |
263 ms |
9424 KB |
Output is correct |
| 5 |
Correct |
376 ms |
15676 KB |
Output is correct |
| 6 |
Correct |
807 ms |
12376 KB |
Output is correct |
| 7 |
Correct |
1336 ms |
14036 KB |
Output is correct |
| 8 |
Correct |
964 ms |
34556 KB |
Output is correct |
| 9 |
Correct |
1871 ms |
27544 KB |
Output is correct |
| 10 |
Correct |
3327 ms |
48412 KB |
Output is correct |
| 11 |
Correct |
2860 ms |
25860 KB |
Output is correct |
| 12 |
Correct |
1193 ms |
29088 KB |
Output is correct |
| 13 |
Correct |
2148 ms |
32136 KB |
Output is correct |
| 14 |
Correct |
2384 ms |
31980 KB |
Output is correct |
| 15 |
Correct |
7429 ms |
49668 KB |
Output is correct |
| 16 |
Execution timed out |
8058 ms |
82388 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8023 ms |
75940 KB |
Time limit exceeded |
