This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int N, R, Q;
int SQRT = 450;
int region[200000];
vector<vector<int>> AdjList;
vector<int> EulerTours;
int enter[200000];
int out[200000];
//unordered_map<int, int> freqRegions;
void dfs(int node){
//cout << node << endl;
EulerTours.push_back(node);
enter[node] = EulerTours.size()-1;
for(int son: AdjList[node]){
dfs(son);
}
out[node] = EulerTours.size()-1;
}
/*
void rSmall(){
int r;
freqRegions.reserve(512);
vector<vector<int>> dp(R, vector<int>(R, 0));
preProcess(0, dp);
int r1, r2;
while(Q--){
cin >> r1 >> r2;
r1--; r2--;
cout << dp[r1][r2] << endl;
}
}*/
void rBig(){
//vector<map<int, int>> blocks(500);
vector<vector<int>> employees(R);
for(int i = 0; i < N; ++i){
employees[region[i]].push_back(i);
int B = i/SQRT;
//blocks[R][region[EulerTours[i]]]++;
}
int r1, r2;
while(Q--){
cin >> r1 >> r2;
r1--; r2--;
int ans = 0;
for(int i: employees[r1]){
for(int j: employees[r2]){
if(enter[i]<enter[j] && out[i]>=out[j])ans++;
}
}
cout << ans << endl;
}
}
int main(){
int p;
cin >> N >> R >> Q;
AdjList = vector<vector<int>>(N);
for(int i = 0; i < N; ++i){
if(i){
cin >> p;
p--;
AdjList[p].push_back(i);
}
cin >> region[i];
region[i]--;
}
dfs(0);
/*
for(int i = 0; i < N; ++i) cout << EulerTours[i] << " ";
cout << endl;*/
/*
if(R <= 1000) rSmall();
else rBig();*/
rBig();
return 0;
}
Compilation message (stderr)
regions.cpp: In function 'void rBig()':
regions.cpp:44:7: warning: unused variable 'B' [-Wunused-variable]
44 | int B = i/SQRT;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |