oj.uz

Submission #735655

# Submission time Handle Problem Language Result Execution time Memory
735655 2023-05-04T12:35:38 Z Ahmed57 Regions (IOI09_regions) C++14
65 / 100
 8000 ms 26280 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= 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);
        }
    }
    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){
      |            ~~~~~~~~~~~^~~

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 4916 KB Output is correct
3 Correct 5 ms 4944 KB Output is correct
4 Correct 7 ms 4944 KB Output is correct
5 Correct 11 ms 4944 KB Output is correct
6 Correct 23 ms 5072 KB Output is correct
7 Correct 20 ms 5072 KB Output is correct
8 Correct 38 ms 5072 KB Output is correct
9 Correct 58 ms 5456 KB Output is correct
10 Correct 87 ms 5584 KB Output is correct
11 Correct 167 ms 5968 KB Output is correct
12 Correct 179 ms 6480 KB Output is correct
13 Correct 248 ms 6364 KB Output is correct
14 Correct 307 ms 6864 KB Output is correct
15 Correct 483 ms 8756 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1958 ms 10168 KB Output is correct
2 Correct 2468 ms 9528 KB Output is correct
3 Correct 3565 ms 11860 KB Output is correct
4 Correct 458 ms 7216 KB Output is correct
5 Correct 566 ms 8456 KB Output is correct
6 Correct 1773 ms 8728 KB Output is correct
7 Correct 3144 ms 10156 KB Output is correct
8 Correct 3224 ms 14048 KB Output is correct
9 Correct 5018 ms 16364 KB Output is correct
10 Correct 7928 ms 20220 KB Output is correct
11 Execution timed out 8006 ms 17940 KB Time limit exceeded
12 Execution timed out 8089 ms 18648 KB Time limit exceeded
13 Execution timed out 8035 ms 18464 KB Time limit exceeded
14 Execution timed out 8064 ms 21220 KB Time limit exceeded
15 Execution timed out 8022 ms 21632 KB Time limit exceeded
16 Execution timed out 8089 ms 24584 KB Time limit exceeded
17 Execution timed out 8018 ms 26280 KB Time limit exceeded