oj.uz

Submission #735641

# Submission time Handle Problem Language Result Execution time Memory
735641 2023-05-04T12:26:59 Z Ahmed57 Regions (IOI09_regions) C++14
30 / 100
 8000 ms 131072 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= 1;
    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 4 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 8 ms 4944 KB Output is correct
5 Correct 11 ms 4988 KB Output is correct
6 Correct 31 ms 6096 KB Output is correct
7 Correct 29 ms 5704 KB Output is correct
8 Correct 64 ms 5968 KB Output is correct
9 Correct 111 ms 7900 KB Output is correct
10 Correct 329 ms 8936 KB Output is correct
11 Correct 346 ms 8124 KB Output is correct
12 Correct 719 ms 10152 KB Output is correct
13 Correct 660 ms 9000 KB Output is correct
14 Correct 567 ms 7808 KB Output is correct
15 Correct 669 ms 9720 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 10968 KB Output is correct
2 Correct 2229 ms 10372 KB Output is correct
3 Correct 2638 ms 13944 KB Output is correct
4 Runtime error 4490 ms 131072 KB Execution killed with signal 9
5 Runtime error 4192 ms 131072 KB Execution killed with signal 9
6 Runtime error 4699 ms 131072 KB Execution killed with signal 9
7 Runtime error 5723 ms 131072 KB Execution killed with signal 9
8 Runtime error 7354 ms 131072 KB Execution killed with signal 9
9 Execution timed out 8061 ms 116804 KB Time limit exceeded
10 Runtime error 6714 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8038 ms 114744 KB Time limit exceeded
12 Execution timed out 8023 ms 99724 KB Time limit exceeded
13 Execution timed out 8061 ms 90772 KB Time limit exceeded
14 Execution timed out 8020 ms 114428 KB Time limit exceeded
15 Runtime error 7890 ms 131072 KB Execution killed with signal 9
16 Runtime error 7890 ms 131072 KB Execution killed with signal 9
17 Execution timed out 8061 ms 125496 KB Time limit exceeded