oj.uz

Submission #735661

# Submission time Handle Problem Language Result Execution time Memory
735661 2023-05-04T12:39:34 Z Ahmed57 Regions (IOI09_regions) C++14
70 / 100
 8000 ms 29908 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);
        }
    }
    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: 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 6 ms 4944 KB Output is correct
4 Correct 9 ms 4944 KB Output is correct
5 Correct 11 ms 5076 KB Output is correct
6 Correct 27 ms 5292 KB Output is correct
7 Correct 35 ms 5256 KB Output is correct
8 Correct 41 ms 5312 KB Output is correct
9 Correct 51 ms 5776 KB Output is correct
10 Correct 120 ms 6084 KB Output is correct
11 Correct 158 ms 6576 KB Output is correct
12 Correct 161 ms 7160 KB Output is correct
13 Correct 213 ms 7112 KB Output is correct
14 Correct 315 ms 7728 KB Output is correct
15 Correct 403 ms 9848 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 12016 KB Output is correct
2 Correct 1712 ms 11096 KB Output is correct
3 Correct 2781 ms 15820 KB Output is correct
4 Correct 452 ms 8616 KB Output is correct
5 Correct 490 ms 10408 KB Output is correct
6 Correct 842 ms 10692 KB Output is correct
7 Correct 1024 ms 11160 KB Output is correct
8 Correct 2055 ms 18044 KB Output is correct
9 Correct 4101 ms 24492 KB Output is correct
10 Correct 6876 ms 29908 KB Output is correct
11 Correct 7494 ms 29408 KB Output is correct
12 Execution timed out 8083 ms 18716 KB Time limit exceeded
13 Execution timed out 8032 ms 18584 KB Time limit exceeded
14 Execution timed out 8041 ms 21308 KB Time limit exceeded
15 Execution timed out 8006 ms 21840 KB Time limit exceeded
16 Execution timed out 8037 ms 24588 KB Time limit exceeded
17 Execution timed out 8025 ms 26476 KB Time limit exceeded