oj.uz

Submission #735690

# Submission time Handle Problem Language Result Execution time Memory
735690 2023-05-04T13:06:29 Z Ahmed57 Regions (IOI09_regions) C++14
0 / 100
 8000 ms 25564 KB 
#include <bits/stdc++.h>

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;
}
long long 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(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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<long long>> 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++){
                long long 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){
            long long 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.find(make_pair(a,b))==mp.end()){
            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<<"\n";
            }else{
            cout<<mp[{a,b}]-1<<"\n";
            }
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if(r[i].size()>=b){
      |            ~~~~~~~~~~~^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 4944 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 4944 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 4944 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 4944 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 4944 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 5072 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 5072 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 5072 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 5456 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 5488 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 5744 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 6224 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 5968 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 6520 KB Time limit exceeded (wall clock)
15 Execution timed out 18 ms 8168 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 308 ms 9244 KB Time limit exceeded (wall clock)
2 Execution timed out 372 ms 8456 KB Time limit exceeded (wall clock)
3 Execution timed out 366 ms 10652 KB Time limit exceeded (wall clock)
4 Execution timed out 20 ms 6736 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 8004 KB Time limit exceeded (wall clock)
6 Execution timed out 2364 ms 10968 KB Time limit exceeded (wall clock)
7 Execution timed out 28 ms 9320 KB Time limit exceeded (wall clock)
8 Execution timed out 562 ms 13532 KB Time limit exceeded (wall clock)
9 Execution timed out 86 ms 14296 KB Time limit exceeded (wall clock)
10 Execution timed out 64 ms 18244 KB Time limit exceeded (wall clock)
11 Execution timed out 79 ms 14824 KB Time limit exceeded (wall clock)
12 Execution timed out 8057 ms 16340 KB Time limit exceeded
13 Execution timed out 8087 ms 16300 KB Time limit exceeded
14 Execution timed out 8089 ms 19812 KB Time limit exceeded
15 Execution timed out 8019 ms 19084 KB Time limit exceeded
16 Execution timed out 8025 ms 22344 KB Time limit exceeded
17 Execution timed out 8026 ms 25564 KB Time limit exceeded