#include<bits/stdc++.h>
using namespace std;
int N, R, Q;
int SQRT = 450;
int region[200000];
vector<vector<int>> AdjList;
vector<int> EulerTours;
vector<int> visited;
int enter[200000];
int out[200000];
unordered_map<int, int> freqRegions;
void dfs(int node){
visited[node] = 1;
//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));
pair<pair<int, int>, pair<int, int>> queries[N];
for(int i = 0; i < N; ++i){
queries[i] = {{enter[i]/SQRT, -out[i]}, {enter[i], i}};
}
sort(queries, queries+N);
int left = 0; int right = 0;
freqRegions[EulerTours[0]] = 1;
for(int i = 0; i < N; ++i){
int qR = - queries[i].first.second;
int qL = queries[i].second.first;
while(right < qR){
right++;
r = region[EulerTours[right]];
freqRegions[r]++;
}while(right > qR){
r = region[EulerTours[right]];
freqRegions[r]--;
right--;
}
while(left < qL){
r = region[EulerTours[left]];
freqRegions[r]--;
left++;
}while(left > qL){
left--;
r = region[EulerTours[left]];
freqRegions[r]++;
}
int actualReg = region[queries[i].second.second];
for(int i = 0; i < R; ++i){
dp[actualReg][i] += freqRegions[i];
}
}
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]){
int l = enter[i];
int r = out[i];
//cout << i << " " << l << " " << r << endl;
while(l % SQRT != 0 and l <= r){
if(region[EulerTours[l]] == r2)ans++;
l++;
}
int bR = r/SQRT;
while(bR*SQRT <= r and l<=r){
if(region[EulerTours[r]] == r2) ans++;
r--;
}
int bL = l/SQRT;
while(bL < bR){
ans += blocks[bL][r2];
bL++;
}
}
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]--;
}
visited = vector<int>(N, 0);
dfs(0);
/*
for(int i = 0; i < N; ++i) cout << EulerTours[i] << " ";
cout << endl;*/
/*
if(R <= 500) rSmall();
else rBig();*/
rBig();
return 0;
}
Compilation message
regions.cpp: In function 'void rBig()':
regions.cpp:76:7: warning: unused variable 'B' [-Wunused-variable]
76 | int B = i/SQRT;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
3 ms |
336 KB |
Output is correct |
5 |
Incorrect |
6 ms |
336 KB |
Output isn't correct |
6 |
Incorrect |
20 ms |
464 KB |
Output isn't correct |
7 |
Incorrect |
32 ms |
464 KB |
Output isn't correct |
8 |
Incorrect |
33 ms |
544 KB |
Output isn't correct |
9 |
Incorrect |
139 ms |
1080 KB |
Output isn't correct |
10 |
Incorrect |
95 ms |
1464 KB |
Output isn't correct |
11 |
Incorrect |
254 ms |
1976 KB |
Output isn't correct |
12 |
Incorrect |
730 ms |
3080 KB |
Output isn't correct |
13 |
Incorrect |
189 ms |
2684 KB |
Output isn't correct |
14 |
Incorrect |
468 ms |
3276 KB |
Output isn't correct |
15 |
Incorrect |
5895 ms |
6456 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
8087 ms |
8244 KB |
Time limit exceeded |
2 |
Execution timed out |
8006 ms |
7396 KB |
Time limit exceeded |
3 |
Execution timed out |
8085 ms |
11516 KB |
Time limit exceeded |
4 |
Runtime error |
16 ms |
4944 KB |
Execution killed with signal 11 |
5 |
Runtime error |
32 ms |
8644 KB |
Execution killed with signal 11 |
6 |
Runtime error |
27 ms |
8632 KB |
Execution killed with signal 11 |
7 |
Runtime error |
37 ms |
11092 KB |
Execution killed with signal 11 |
8 |
Runtime error |
68 ms |
22404 KB |
Execution killed with signal 11 |
9 |
Runtime error |
94 ms |
24736 KB |
Execution killed with signal 11 |
10 |
Runtime error |
110 ms |
35952 KB |
Execution killed with signal 11 |
11 |
Runtime error |
112 ms |
26820 KB |
Execution killed with signal 11 |
12 |
Runtime error |
114 ms |
29952 KB |
Execution killed with signal 11 |
13 |
Runtime error |
119 ms |
30312 KB |
Execution killed with signal 11 |
14 |
Runtime error |
118 ms |
29928 KB |
Execution killed with signal 11 |
15 |
Runtime error |
114 ms |
38548 KB |
Execution killed with signal 11 |
16 |
Runtime error |
123 ms |
50000 KB |
Execution killed with signal 11 |
17 |
Runtime error |
130 ms |
47192 KB |
Execution killed with signal 11 |