oj.uz

Submission #735648

# Submission time Handle Problem Language Result Execution time Memory
735648 2023-05-04T12:32:54 Z Ahmed57 Regions (IOI09_regions) C++14
70 / 100
 8000 ms 27840 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= 600;
    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 4944 KB Output is correct
3 Correct 5 ms 4944 KB Output is correct
4 Correct 7 ms 4944 KB Output is correct
5 Correct 9 ms 4944 KB Output is correct
6 Correct 20 ms 5072 KB Output is correct
7 Correct 30 ms 5072 KB Output is correct
8 Correct 36 ms 5072 KB Output is correct
9 Correct 51 ms 5416 KB Output is correct
10 Correct 61 ms 5688 KB Output is correct
11 Correct 152 ms 5908 KB Output is correct
12 Correct 192 ms 6440 KB Output is correct
13 Correct 225 ms 6352 KB Output is correct
14 Correct 422 ms 6916 KB Output is correct
15 Correct 465 ms 8752 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1969 ms 10192 KB Output is correct
2 Correct 2409 ms 9596 KB Output is correct
3 Correct 4019 ms 11860 KB Output is correct
4 Correct 408 ms 7216 KB Output is correct
5 Correct 484 ms 8428 KB Output is correct
6 Correct 1926 ms 8756 KB Output is correct
7 Correct 2816 ms 10248 KB Output is correct
8 Correct 2926 ms 14108 KB Output is correct
9 Correct 4596 ms 16320 KB Output is correct
10 Correct 6618 ms 20168 KB Output is correct
11 Correct 6562 ms 17796 KB Output is correct
12 Execution timed out 8012 ms 18560 KB Time limit exceeded
13 Execution timed out 8016 ms 18700 KB Time limit exceeded
14 Execution timed out 8077 ms 21752 KB Time limit exceeded
15 Execution timed out 8028 ms 21560 KB Time limit exceeded
16 Execution timed out 8071 ms 25112 KB Time limit exceeded
17 Execution timed out 8084 ms 27840 KB Time limit exceeded