oj.uz

Submission #735666

# Submission time Handle Problem Language Result Execution time Memory
735666 2023-05-04T12:43:31 Z Ahmed57 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 22360 KB 
#pragma GCC optimize(Ofast)
#include <bits/stdc++.h>

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(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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:1:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
    1 | #pragma GCC optimize(Ofast)
      |                      ^~~~~
regions.cpp: In function 'int main()':
regions.cpp:48:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if(r[i].size()>=b){
      |            ~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 10 ms 4944 KB Output is correct
5 Correct 7 ms 4944 KB Output is correct
6 Correct 11 ms 5072 KB Output is correct
7 Correct 36 ms 5072 KB Output is correct
8 Correct 39 ms 5072 KB Output is correct
9 Correct 68 ms 5456 KB Output is correct
10 Correct 82 ms 5524 KB Output is correct
11 Correct 115 ms 5668 KB Output is correct
12 Correct 149 ms 6132 KB Output is correct
13 Correct 270 ms 5816 KB Output is correct
14 Correct 376 ms 6408 KB Output is correct
15 Correct 495 ms 8016 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 304 ms 8920 KB Time limit exceeded (wall clock)
2 Execution timed out 321 ms 8028 KB Time limit exceeded (wall clock)
3 Execution timed out 338 ms 10340 KB Time limit exceeded (wall clock)
4 Correct 429 ms 6700 KB Output is correct
5 Correct 535 ms 7920 KB Output is correct
6 Correct 1746 ms 7888 KB Output is correct
7 Correct 2915 ms 8944 KB Output is correct
8 Correct 2571 ms 12512 KB Output is correct
9 Correct 4097 ms 13724 KB Output is correct
10 Correct 6285 ms 17480 KB Output is correct
11 Correct 6126 ms 14148 KB Output is correct
12 Execution timed out 8018 ms 15256 KB Time limit exceeded
13 Execution timed out 8053 ms 15412 KB Time limit exceeded
14 Execution timed out 8068 ms 16888 KB Time limit exceeded
15 Execution timed out 8055 ms 18332 KB Time limit exceeded
16 Execution timed out 8051 ms 21796 KB Time limit exceeded
17 Execution timed out 8070 ms 22360 KB Time limit exceeded