#include <bits/stdc++.h>
using namespace std;
struct query{
int a, b, ind, ans;
};
const int N = 2e5+3;
vector<int> g[N];
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]);
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);
}
for(int e : pos[downs[i].b])downs[i].ans+=Get(tin[e], tout[e]);
}
}
for(int i=0; i<2*N; i++)f[i]=0;
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]);
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);
}
}
for(int e : pos[ups[i].b])ups[i].ans+=Get(0, tin[e]);
}
}
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:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=1; i<downs.size(); i++){
| ~^~~~~~~~~~~~~
regions.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=1; i<ups.size(); i++){
| ~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
2 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 |
2 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 |
2 ms |
9560 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
3 ms |
9816 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
4 ms |
9876 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
5 ms |
9896 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
5 ms |
10328 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
7 ms |
10072 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
7 ms |
10328 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
11 ms |
12768 KB |
Time limit exceeded (wall clock) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
14 ms |
12376 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
17 ms |
11172 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
21 ms |
13972 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
10 ms |
10412 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
10 ms |
11864 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
11 ms |
11172 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
15 ms |
11636 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
22 ms |
15900 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
37 ms |
14692 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
37 ms |
19824 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
40 ms |
13356 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
51 ms |
15780 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
41 ms |
15880 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
52 ms |
15280 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
48 ms |
19288 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
53 ms |
24704 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
46 ms |
23748 KB |
Time limit exceeded (wall clock) |