| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 764188 |
2023-06-23T08:27:18 Z |
a_aguilo |
Regions (IOI09_regions) |
C++14 |
|
8000 ms |
48384 KB |
#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
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 |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
4 ms |
336 KB |
Output is correct |
| 5 |
Correct |
7 ms |
336 KB |
Output is correct |
| 6 |
Correct |
17 ms |
336 KB |
Output is correct |
| 7 |
Correct |
26 ms |
464 KB |
Output is correct |
| 8 |
Correct |
36 ms |
464 KB |
Output is correct |
| 9 |
Correct |
50 ms |
976 KB |
Output is correct |
| 10 |
Correct |
92 ms |
1104 KB |
Output is correct |
| 11 |
Correct |
167 ms |
1488 KB |
Output is correct |
| 12 |
Correct |
155 ms |
2128 KB |
Output is correct |
| 13 |
Correct |
310 ms |
1872 KB |
Output is correct |
| 14 |
Correct |
748 ms |
2592 KB |
Output is correct |
| 15 |
Correct |
604 ms |
5352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8096 ms |
6612 KB |
Time limit exceeded |
| 2 |
Execution timed out |
8087 ms |
5576 KB |
Time limit exceeded |
| 3 |
Execution timed out |
8055 ms |
8784 KB |
Time limit exceeded |
| 4 |
Runtime error |
16 ms |
4712 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
20 ms |
8432 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
37 ms |
8316 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
37 ms |
10564 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
68 ms |
21692 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
100 ms |
23624 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
109 ms |
34496 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
127 ms |
25180 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
129 ms |
28512 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
104 ms |
28824 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
163 ms |
28336 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
115 ms |
36968 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
118 ms |
48384 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
114 ms |
45668 KB |
Execution killed with signal 11 |
