oj.uz

Submission #735679

# Submission time Handle Problem Language Result Execution time Memory
735679 2023-05-04T12:56:01 Z Ahmed57 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 26240 KB 
#pragma GCC optimize("unroll-loops","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;
}
long long 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<long long>> ans,ans2;
    int id = -1;int b= 500;
    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++){
                long long 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){
            long long 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: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 4 ms 4944 KB Output is correct
4 Correct 7 ms 4944 KB Output is correct
5 Correct 10 ms 4944 KB Output is correct
6 Correct 22 ms 5056 KB Output is correct
7 Correct 38 ms 5072 KB Output is correct
8 Correct 36 ms 5072 KB Output is correct
9 Correct 59 ms 5464 KB Output is correct
10 Correct 82 ms 5548 KB Output is correct
11 Correct 145 ms 5840 KB Output is correct
12 Correct 131 ms 6240 KB Output is correct
13 Correct 176 ms 5948 KB Output is correct
14 Correct 354 ms 6520 KB Output is correct
15 Correct 409 ms 8356 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 260 ms 9392 KB Time limit exceeded (wall clock)
2 Execution timed out 374 ms 8484 KB Time limit exceeded (wall clock)
3 Execution timed out 357 ms 10772 KB Time limit exceeded (wall clock)
4 Correct 383 ms 6924 KB Output is correct
5 Correct 394 ms 8172 KB Output is correct
6 Execution timed out 2305 ms 10964 KB Time limit exceeded (wall clock)
7 Correct 2326 ms 9228 KB Output is correct
8 Execution timed out 550 ms 13672 KB Time limit exceeded (wall clock)
9 Correct 3953 ms 14344 KB Output is correct
10 Correct 6390 ms 18536 KB Output is correct
11 Correct 6598 ms 14792 KB Output is correct
12 Execution timed out 8022 ms 16456 KB Time limit exceeded
13 Execution timed out 8087 ms 16460 KB Time limit exceeded
14 Execution timed out 8096 ms 20116 KB Time limit exceeded
15 Execution timed out 8082 ms 19728 KB Time limit exceeded
16 Execution timed out 8082 ms 23264 KB Time limit exceeded
17 Execution timed out 8089 ms 26240 KB Time limit exceeded