oj.uz

Submission #735645

# Submission time Handle Problem Language Result Execution time Memory
735645 2023-05-04T12:30:16 Z Ahmed57 Regions (IOI09_regions) C++14
70 / 100
 8000 ms 28128 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= 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++){
                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 4 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 13 ms 4944 KB Output is correct
6 Correct 26 ms 5072 KB Output is correct
7 Correct 32 ms 5072 KB Output is correct
8 Correct 59 ms 5072 KB Output is correct
9 Correct 66 ms 5456 KB Output is correct
10 Correct 102 ms 5668 KB Output is correct
11 Correct 174 ms 5968 KB Output is correct
12 Correct 174 ms 6480 KB Output is correct
13 Correct 204 ms 6352 KB Output is correct
14 Correct 379 ms 6884 KB Output is correct
15 Correct 410 ms 8656 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1952 ms 10220 KB Output is correct
2 Correct 1957 ms 9532 KB Output is correct
3 Correct 3401 ms 11792 KB Output is correct
4 Correct 383 ms 7228 KB Output is correct
5 Correct 618 ms 8504 KB Output is correct
6 Correct 3729 ms 11620 KB Output is correct
7 Correct 2783 ms 10248 KB Output is correct
8 Correct 2912 ms 14632 KB Output is correct
9 Correct 4208 ms 16312 KB Output is correct
10 Correct 7050 ms 20236 KB Output is correct
11 Correct 7733 ms 17872 KB Output is correct
12 Execution timed out 8082 ms 19244 KB Time limit exceeded
13 Execution timed out 8055 ms 18808 KB Time limit exceeded
14 Execution timed out 8042 ms 22928 KB Time limit exceeded
15 Execution timed out 8074 ms 21708 KB Time limit exceeded
16 Execution timed out 8074 ms 24812 KB Time limit exceeded
17 Execution timed out 8076 ms 28128 KB Time limit exceeded