# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1042853 |
2024-08-03T13:10:29 Z |
ThommyDB |
Regions (IOI09_regions) |
C++17 |
|
3110 ms |
25764 KB |
#include<bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> home, rid;
vector<vector<int>> reverse_super, conn, tot;
vector<pair<pair<int, int>, int>> euler;
int timer = 0;
void euler_tour(int at) {
euler[at].first.first = timer;
euler[timer].second = at;
conn[home[at]].push_back(timer);
timer++;
for (int u : reverse_super[at]) {
euler_tour(u);
}
euler[at].first.second = timer;
}
void dfs(int x, int parreg, int parc){
if(home[x]==parreg){
parc++;
}
tot[rid[parreg]][home[x]]+=parc;
for(auto u : reverse_super[x]) dfs(u, parreg, parc);
}
signed main(){
cin >> n >> r >> q;
home.resize(n+1);
reverse_super.resize(n+1);
euler.resize(n+1);
conn.resize(r+1);
rid.resize(r+1);
cin >> home[0]; home[0]--;
for(int i = 1; i < n; i++){
int super;
cin >> super >> home[i];super--; home[i]--;
reverse_super[super].push_back(i);
}
euler_tour(0);
int a=0;
for(int i=0;i<r;i++){
if(conn[i].size()>1000){
rid[i]=a;
a++;
tot.push_back(vector<int>(r));
dfs(0, i, 0);
}
}
int r1, r2;
for(int i = 0; i < q; i++){
cin >> r1 >> r2;r1--;r2--;
if(conn[r1].size()>1000){
cout << tot[rid[r1]][r2] << "\n";
continue;
}
int ans = 0;
for(auto u : conn[r1]){
ans +=lower_bound(conn[r2].begin(), conn[r2].end(), euler[euler[u].second].first.second)
-lower_bound(conn[r2].begin(), conn[r2].end(), euler[euler[u].second].first.first);
}
cout << ans << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
2 ms |
344 KB |
Output is correct |
5 |
Correct |
3 ms |
344 KB |
Output is correct |
6 |
Correct |
10 ms |
344 KB |
Output is correct |
7 |
Correct |
12 ms |
344 KB |
Output is correct |
8 |
Correct |
14 ms |
600 KB |
Output is correct |
9 |
Correct |
22 ms |
856 KB |
Output is correct |
10 |
Correct |
51 ms |
1112 KB |
Output is correct |
11 |
Correct |
64 ms |
1580 KB |
Output is correct |
12 |
Correct |
75 ms |
2136 KB |
Output is correct |
13 |
Correct |
91 ms |
1956 KB |
Output is correct |
14 |
Correct |
149 ms |
2656 KB |
Output is correct |
15 |
Correct |
173 ms |
4692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1375 ms |
6744 KB |
Output is correct |
2 |
Correct |
1581 ms |
5696 KB |
Output is correct |
3 |
Correct |
2074 ms |
8908 KB |
Output is correct |
4 |
Correct |
181 ms |
2768 KB |
Output is correct |
5 |
Correct |
226 ms |
4220 KB |
Output is correct |
6 |
Correct |
930 ms |
4536 KB |
Output is correct |
7 |
Correct |
1130 ms |
5996 KB |
Output is correct |
8 |
Correct |
944 ms |
10604 KB |
Output is correct |
9 |
Correct |
1638 ms |
12896 KB |
Output is correct |
10 |
Correct |
3110 ms |
17328 KB |
Output is correct |
11 |
Correct |
2597 ms |
14292 KB |
Output is correct |
12 |
Correct |
965 ms |
15668 KB |
Output is correct |
13 |
Correct |
1362 ms |
15884 KB |
Output is correct |
14 |
Correct |
1674 ms |
16812 KB |
Output is correct |
15 |
Correct |
2301 ms |
20232 KB |
Output is correct |
16 |
Correct |
2368 ms |
25764 KB |
Output is correct |
17 |
Correct |
2221 ms |
25352 KB |
Output is correct |