# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
647348 |
2022-10-02T09:27:54 Z |
Karuk |
Regions (IOI09_regions) |
C++14 |
|
4999 ms |
106688 KB |
#include<bits/stdc++.h>
using namespace std;
const int bucket=450;
int parent[200001];
vector<int>children[200001];
int reg[200001];///regions
vector<int>indexx[25001];
vector<int>regions[25001];
int ticker=0;
int beg[200001],en[200001];
void dfs(int n) {
indexx[reg[n]].push_back(ticker);
beg[n]=ticker++;
for(int i:children[n]) {
dfs(i);
}
en[n]=ticker-1;
}
vector<int>large;
int num[25001];
map<pair<int,int>,int>ans;
void dfs1(int n) {
for(int i:large) {
ans[{i,reg[n]}]+=num[i];
}
num[reg[n]]++;
for(int i:children[n]) {
dfs1(i);
}
num[reg[n]]--;
}
int main() {
int n,r,q;cin>>n>>r>>q;
cin>>reg[1];
regions[reg[1]].push_back(1);
for(int i=2;i<=n;i++) {
cin>>parent[i]>>reg[i];
children[parent[i]].push_back(i);
regions[reg[i]].push_back(i);
}
dfs(1);
for(int i=1;i<=r;i++) {
if(indexx[i].size()>=bucket)large.push_back(i);
}
dfs1(1);
for(int i=0;i<q;i++) {
int x,y;cin>>x>>y;
if(indexx[x].size()>=bucket)cout<<ans[{x,y}]<<endl;
else {
int anss=0;
for(int ind:regions[x]) {
int pos1=upper_bound(indexx[y].begin(),indexx[y].end(),beg[ind])-indexx[y].begin();
int pos2=upper_bound(indexx[y].begin(),indexx[y].end(),en[ind])-indexx[y].begin();
anss+=pos2-pos1;
}
cout<<anss<<endl;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6096 KB |
Output is correct |
2 |
Correct |
3 ms |
6096 KB |
Output is correct |
3 |
Correct |
6 ms |
6096 KB |
Output is correct |
4 |
Correct |
8 ms |
6096 KB |
Output is correct |
5 |
Correct |
12 ms |
6224 KB |
Output is correct |
6 |
Correct |
19 ms |
6224 KB |
Output is correct |
7 |
Correct |
35 ms |
6224 KB |
Output is correct |
8 |
Correct |
36 ms |
6224 KB |
Output is correct |
9 |
Correct |
43 ms |
6992 KB |
Output is correct |
10 |
Correct |
86 ms |
6736 KB |
Output is correct |
11 |
Correct |
132 ms |
7120 KB |
Output is correct |
12 |
Correct |
152 ms |
7888 KB |
Output is correct |
13 |
Correct |
127 ms |
7248 KB |
Output is correct |
14 |
Correct |
307 ms |
7888 KB |
Output is correct |
15 |
Correct |
285 ms |
12880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1736 ms |
12112 KB |
Output is correct |
2 |
Correct |
2244 ms |
10312 KB |
Output is correct |
3 |
Correct |
3015 ms |
15328 KB |
Output is correct |
4 |
Correct |
330 ms |
8008 KB |
Output is correct |
5 |
Correct |
437 ms |
11168 KB |
Output is correct |
6 |
Correct |
884 ms |
32724 KB |
Output is correct |
7 |
Correct |
1769 ms |
19492 KB |
Output is correct |
8 |
Correct |
2159 ms |
82432 KB |
Output is correct |
9 |
Correct |
1996 ms |
17432 KB |
Output is correct |
10 |
Correct |
4999 ms |
106688 KB |
Output is correct |
11 |
Correct |
4017 ms |
16484 KB |
Output is correct |
12 |
Correct |
1556 ms |
19572 KB |
Output is correct |
13 |
Correct |
2360 ms |
20776 KB |
Output is correct |
14 |
Correct |
2995 ms |
41652 KB |
Output is correct |
15 |
Correct |
3213 ms |
29488 KB |
Output is correct |
16 |
Correct |
2722 ms |
42436 KB |
Output is correct |
17 |
Correct |
3591 ms |
61640 KB |
Output is correct |