# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
415752 |
2021-06-01T13:01:31 Z |
Antekb |
Regions (IOI09_regions) |
C++14 |
|
4951 ms |
130604 KB |
#include<bits/stdc++.h>
using namespace std;
const int N=500, M=25000, K=200000;
vector<int> E[K];
int R[K], pre[K], post[K], ile3[M], sta[M], sta2[M];
vector<int> pocz[M], kon[M];
int ile[M][N], ile2[M][N], gdzie[M];
vector<int> duz;
int wsk=0;
void dfs(int v){
//cout<<v<<"q\n";
pre[v]=wsk++;
pocz[R[v]].push_back(pre[v]);
sta[R[v]]++;
sta2[R[v]]++;
for(int i=0; i<duz.size(); i++){
ile[R[v]][i]-=sta[duz[i]];
ile2[R[v]][i]+=sta2[duz[i]];
}
for(int u:E[v]){
dfs(u);
}
for(int i=0; i<duz.size(); i++){
ile[R[v]][i]+=sta[duz[i]];
}
sta2[R[v]]--;
post[v]=wsk;
kon[R[v]].push_back(post[v]);
}
int main(){
int n, r, q;
cin>>n>>r>>q;
for(int i=0; i<n ;i++){
int h, p;
if(i){
cin>>p;
p--;
E[p].push_back(i);
}
cin>>R[i];
--R[i];
ile3[R[i]]++;
}
for(int i=0; i<r; i++){
if(ile3[i]>=N){
duz.push_back(i);
gdzie[i]=duz.size();
}
}
dfs(0);
for(int i=0;i<q; i++){
int r1, r2;
cin>>r1>>r2;
r1--;
r2--;
if(gdzie[r1]){
cout<<ile2[r2][gdzie[r1]-1];
}
else if(gdzie[r2]){
cout<<ile[r1][gdzie[r2]-1];
}
else{
//cout<<"a";
int ans=0;
for(int i=0; i<pocz[r1].size(); i++){
// cout<<"b";
ans+=(lower_bound(pocz[r2].begin(), pocz[r2].end(), kon[r1][i])-lower_bound(pocz[r2].begin(), pocz[r2].end(), pocz[r1][i]));
}
cout<<ans;
}
cout<<endl;
}
}
Compilation message
regions.cpp: In function 'void dfs(int)':
regions.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i=0; i<duz.size(); i++){
| ~^~~~~~~~~~~
regions.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0; i<duz.size(); i++){
| ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:34:13: warning: unused variable 'h' [-Wunused-variable]
34 | int h, p;
| ^
regions.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0; i<pocz[r1].size(); i++){
| ~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6148 KB |
Output is correct |
2 |
Correct |
6 ms |
6140 KB |
Output is correct |
3 |
Correct |
7 ms |
6088 KB |
Output is correct |
4 |
Correct |
12 ms |
6088 KB |
Output is correct |
5 |
Correct |
14 ms |
6216 KB |
Output is correct |
6 |
Correct |
21 ms |
6216 KB |
Output is correct |
7 |
Correct |
33 ms |
6204 KB |
Output is correct |
8 |
Correct |
35 ms |
6216 KB |
Output is correct |
9 |
Correct |
63 ms |
6784 KB |
Output is correct |
10 |
Correct |
130 ms |
6676 KB |
Output is correct |
11 |
Correct |
182 ms |
6984 KB |
Output is correct |
12 |
Correct |
216 ms |
7624 KB |
Output is correct |
13 |
Correct |
268 ms |
7152 KB |
Output is correct |
14 |
Correct |
365 ms |
7744 KB |
Output is correct |
15 |
Correct |
302 ms |
11584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1698 ms |
12084 KB |
Output is correct |
2 |
Correct |
1388 ms |
10640 KB |
Output is correct |
3 |
Correct |
2406 ms |
14784 KB |
Output is correct |
4 |
Correct |
265 ms |
7988 KB |
Output is correct |
5 |
Correct |
459 ms |
10268 KB |
Output is correct |
6 |
Correct |
1249 ms |
36372 KB |
Output is correct |
7 |
Correct |
1730 ms |
10428 KB |
Output is correct |
8 |
Correct |
1525 ms |
56464 KB |
Output is correct |
9 |
Correct |
2066 ms |
16404 KB |
Output is correct |
10 |
Correct |
4610 ms |
23564 KB |
Output is correct |
11 |
Correct |
4951 ms |
15908 KB |
Output is correct |
12 |
Correct |
1425 ms |
78880 KB |
Output is correct |
13 |
Correct |
2214 ms |
79512 KB |
Output is correct |
14 |
Correct |
2747 ms |
94184 KB |
Output is correct |
15 |
Correct |
4054 ms |
121656 KB |
Output is correct |
16 |
Correct |
3768 ms |
130604 KB |
Output is correct |
17 |
Correct |
3716 ms |
107900 KB |
Output is correct |