oj.uz

Submission #735664

# Submission time Handle Problem Language Result Execution time Memory
735664 2023-05-04T12:42:27 Z Ahmed57 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 27224 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= 800;
    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);
        }
    }
    map<pair<int,int>,int> mp;
    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{
            if(mp[{a,b}]!=0){
                cout<<mp[{a,b}]-1<<endl;continue;
            }
            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);
            }
            mp[{a,b}] = val+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 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 8 ms 4944 KB Output is correct
5 Correct 10 ms 5072 KB Output is correct
6 Correct 19 ms 5156 KB Output is correct
7 Correct 30 ms 5216 KB Output is correct
8 Correct 56 ms 5300 KB Output is correct
9 Correct 64 ms 5676 KB Output is correct
10 Correct 100 ms 5960 KB Output is correct
11 Correct 188 ms 6304 KB Output is correct
12 Correct 113 ms 6864 KB Output is correct
13 Correct 265 ms 6688 KB Output is correct
14 Correct 292 ms 7320 KB Output is correct
15 Correct 455 ms 9016 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 204 ms 8912 KB Time limit exceeded (wall clock)
2 Execution timed out 320 ms 8136 KB Time limit exceeded (wall clock)
3 Execution timed out 335 ms 10160 KB Time limit exceeded (wall clock)
4 Correct 286 ms 8292 KB Output is correct
5 Correct 292 ms 9856 KB Output is correct
6 Correct 792 ms 9832 KB Output is correct
7 Correct 824 ms 10080 KB Output is correct
8 Correct 1822 ms 16432 KB Output is correct
9 Correct 4359 ms 21792 KB Output is correct
10 Correct 7042 ms 27224 KB Output is correct
11 Correct 7561 ms 25680 KB Output is correct
12 Execution timed out 8073 ms 15364 KB Time limit exceeded
13 Execution timed out 8041 ms 15340 KB Time limit exceeded
14 Execution timed out 8098 ms 16392 KB Time limit exceeded
15 Execution timed out 8028 ms 18296 KB Time limit exceeded
16 Execution timed out 8073 ms 21492 KB Time limit exceeded
17 Execution timed out 8102 ms 21624 KB Time limit exceeded