#include <bits/stdc++.h>
using namespace std;
struct query{
int a, b, ind, ans;
};
const int N = 2e5+3;
vector<int> g[N];
set<pair<int, int>> answered;
map<pair<int, int>, int> answer;
int a[N], tin[N], tout[N], cnt[N];
int f[2*N];
int timer=1;
void dfs(int v, int p){
tin[v]=timer++;
for(int to : g[v])dfs(to, v);
tout[v]=timer++;
}
bool cmp(query A, query B){
return A.a < B.a;
}
bool cmp2(query A, query B){
return A.ind<B.ind;
}
void Update(int ind, int val){
for(int i=ind; i<2*N; i+=i&-i)f[i]+=val;
}
int Get(int ind){
int ret=0;
for(int i=ind; i>0; i-=i&-i)ret+=f[i];
return ret;
}
int Get(int l, int r){
return Get(r)-Get(l-1);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, r, q;
cin >> n >> r >> q;
cin >> a[1];
cnt[a[1]]++;
for(int i=2; i<=n; i++){
int x;
cin >> x >> a[i];
cnt[a[i]]++;
g[x].push_back(i);
}
dfs(1, 1);
vector<query> ups;
vector<query> downs;
for(int i=0; i<q; i++){
int u, v;
cin >> u >> v;
if(cnt[u]>cnt[v])ups.push_back({u, v, i, 0});
else downs.push_back({v, u, i, 0});
}
sort(downs.begin(), downs.end(), cmp);
sort(ups.begin(), ups.end(), cmp);
vector<int> pos[r+1];
for(int i=1; i<=n; i++){
pos[a[i]].push_back(i);
}
if(downs.size()){
for(int e : pos[downs[0].a])Update(tin[e], 1);
for(int e : pos[downs[0].b])downs[0].ans+=Get(tin[e], tout[e]);
answered.insert({downs[0]. a, downs[0]. b});
answer[{downs[0].a, downs[0].b}] = downs[0].ans;
for(int i=1; i<downs.size(); i++){
if(downs[i].a!=downs[i-1].a){
for(int e : pos[downs[i-1].a])Update(tin[e], -1);
for(int e : pos[downs[i].a])Update(tin[e], 1);
}
if(answered.find({downs[i].a, downs[i].b})!=answered.end()){
downs[i].ans = answer[{downs[i].a, downs[i].b}];
continue;
}
for(int e : pos[downs[i].b])downs[i].ans+=Get(tin[e], tout[e]);
answered.insert({downs[i].a, downs[i].b});
answer[{downs[i].a, downs[i].b}] = downs[i].ans;
}
}
for(int i=0; i<2*N; i++)f[i]=0;
answered.clear();
answer.clear();
if(ups.size()){
for(int e : pos[ups[0].a]){
Update(tin[e], 1);
Update(tout[e], -1);
}
for(int e : pos[ups[0].b])ups[0].ans+=Get(0, tin[e]);
answer[{ups[0].a, ups[0].b}] = ups[0].ans;
answered.insert({ups[0].a, ups[0].b});
for(int i=1; i<ups.size(); i++){
if(ups[i].a!=ups[i-1].a){
for(int e : pos[ups[i-1].a]){
Update(tin[e], -1);
Update(tout[e], 1);
}
for(int e : pos[ups[i].a]){
Update(tin[e], 1);
Update(tout[e], -1);
}
}
if(answered.find({ups[i].a, ups[i].b})!=answered.end()){
ups[i].ans=answer[{ups[i].a, ups[i].b}];
continue;
}
for(int e : pos[ups[i].b])ups[i].ans+=Get(0, tin[e]);
answer[{ups[i].a, ups[i].b}] = ups[i].ans;
answered.insert({ups[i].a, ups[i].b});
}
}
vector<query> svi;
for(auto & e : downs)svi.push_back(e);
for(auto & e : ups)svi.push_back(e);
sort(svi.begin(), svi.end(), cmp2);
for(auto & e : svi)cout << e.ans << '\n';
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=1; i<downs.size(); i++){
| ~^~~~~~~~~~~~~
regions.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=1; i<ups.size(); i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
2 ms |
9716 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
6 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
6 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
3 ms |
9560 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
5 ms |
10072 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
5 ms |
9816 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
5 ms |
10112 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
8 ms |
10328 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
8 ms |
9984 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
10 ms |
10328 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
14 ms |
12664 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
16 ms |
12392 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
15 ms |
11088 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
18 ms |
14168 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
10 ms |
10552 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
9 ms |
11876 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
13 ms |
11112 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
13 ms |
11624 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
24 ms |
15872 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
30 ms |
14696 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
32 ms |
19416 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
55 ms |
13392 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
46 ms |
15656 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
43 ms |
16040 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
48 ms |
15336 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
47 ms |
18976 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
52 ms |
25240 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
40 ms |
23944 KB |
Time limit exceeded (wall clock) |
