# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
735648 |
2023-05-04T12:32:54 Z |
Ahmed57 |
Regions (IOI09_regions) |
C++14 |
|
8000 ms |
27840 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
int timer = 0;
int start[200001];
int en[200001];
vector<int> adj[200001];
void dfs(int i){
start[i] = ++timer;
for(auto j:adj[i])dfs(j);
en[i] = timer;
}
int bit[200001];int n;
void add(int x,int v){
while(x<=n){
bit[x]+=v;
x+=(x&-x);
}
}
int sum(int x){
int su = 0;
while(x>=1){
su+=bit[x];
x-=(x&-x);
}
return su;
}
signed main() {
int m,q;
cin>>n>>m>>q;
vector<int> r[m+1];
int x;cin>>x;
r[x].push_back(1);
for(int i = 2;i<=n;i++){
int pr,x;cin>>pr>>x;
adj[pr].push_back(i);
r[x].push_back(i);
}
dfs(1);
vector<vector<int>> ans,ans2;
int id = -1;int b= 600;
int ge[m+1];
vector<int> noob;
for(int i = 1;i<=m;i++)ge[i] = -1;
for(int i = 1;i<=m;i++){
if(r[i].size()>=b){
noob.push_back(i);
ge[i] = ++id;
for(auto j:r[i]){
add(start[j],1);
}
ans.push_back({});
for(int j = 1;j<=m;j++){
int val = 0;
for(auto k:r[j]){
val+=sum(en[k])-sum(start[k]-1);
}
ans.back().push_back(val);
}
for(auto j:r[i]){
add(start[j],-1);
}
}
}
for(int i = 1;i<=m;i++){
for(auto j:r[i]){
add(start[j],1);
}
ans2.push_back({});
for(auto j:noob){
int val = 0;
for(auto k:r[j]){
val+=sum(en[k])-sum(start[k]-1);
}
ans2.back().push_back(val);
}
for(auto j:r[i]){
add(start[j],-1);
}
}
while(q--){
int a,b;cin>>a>>b;
if(ge[b]!=-1)cout<<ans[ge[b]][a-1]<<"\n";
else if(ge[a]!=-1)cout<<ans2[b-1][ge[a]]<<"\n";
else{
for(auto j:r[b]){
add(start[j],1);
}
int val = 0;
for(auto j:r[a]){
val+=sum(en[j])-sum(start[j]-1);
}
for(auto j:r[b]){
add(start[j],-1);
}
cout<<val<<endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
47 | if(r[i].size()>=b){
| ~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
5 ms |
4944 KB |
Output is correct |
4 |
Correct |
7 ms |
4944 KB |
Output is correct |
5 |
Correct |
9 ms |
4944 KB |
Output is correct |
6 |
Correct |
20 ms |
5072 KB |
Output is correct |
7 |
Correct |
30 ms |
5072 KB |
Output is correct |
8 |
Correct |
36 ms |
5072 KB |
Output is correct |
9 |
Correct |
51 ms |
5416 KB |
Output is correct |
10 |
Correct |
61 ms |
5688 KB |
Output is correct |
11 |
Correct |
152 ms |
5908 KB |
Output is correct |
12 |
Correct |
192 ms |
6440 KB |
Output is correct |
13 |
Correct |
225 ms |
6352 KB |
Output is correct |
14 |
Correct |
422 ms |
6916 KB |
Output is correct |
15 |
Correct |
465 ms |
8752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1969 ms |
10192 KB |
Output is correct |
2 |
Correct |
2409 ms |
9596 KB |
Output is correct |
3 |
Correct |
4019 ms |
11860 KB |
Output is correct |
4 |
Correct |
408 ms |
7216 KB |
Output is correct |
5 |
Correct |
484 ms |
8428 KB |
Output is correct |
6 |
Correct |
1926 ms |
8756 KB |
Output is correct |
7 |
Correct |
2816 ms |
10248 KB |
Output is correct |
8 |
Correct |
2926 ms |
14108 KB |
Output is correct |
9 |
Correct |
4596 ms |
16320 KB |
Output is correct |
10 |
Correct |
6618 ms |
20168 KB |
Output is correct |
11 |
Correct |
6562 ms |
17796 KB |
Output is correct |
12 |
Execution timed out |
8012 ms |
18560 KB |
Time limit exceeded |
13 |
Execution timed out |
8016 ms |
18700 KB |
Time limit exceeded |
14 |
Execution timed out |
8077 ms |
21752 KB |
Time limit exceeded |
15 |
Execution timed out |
8028 ms |
21560 KB |
Time limit exceeded |
16 |
Execution timed out |
8071 ms |
25112 KB |
Time limit exceeded |
17 |
Execution timed out |
8084 ms |
27840 KB |
Time limit exceeded |