oj.uz

Submission #735685

# Submission time Handle Problem Language Result Execution time Memory
735685 2023-05-04T13:01:57 Z Ahmed57 Regions (IOI09_regions) C++14
0 / 100
 8000 ms 26064 KB 
#pragma GCC optimize("unroll-loops","Ofast")
#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:48:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if(r[i].size()>=b){
      |            ~~~~~~~~~~~^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 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 3 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 3 ms 5072 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 5456 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 5456 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 5840 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 6160 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 5968 KB Time limit exceeded (wall clock)
14 Execution timed out 11 ms 6480 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 8272 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 249 ms 9240 KB Time limit exceeded (wall clock)
2 Execution timed out 371 ms 8348 KB Time limit exceeded (wall clock)
3 Execution timed out 353 ms 10780 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 6736 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 8112 KB Time limit exceeded (wall clock)
6 Execution timed out 2257 ms 11200 KB Time limit exceeded (wall clock)
7 Execution timed out 30 ms 9268 KB Time limit exceeded (wall clock)
8 Execution timed out 552 ms 13632 KB Time limit exceeded (wall clock)
9 Execution timed out 65 ms 14288 KB Time limit exceeded (wall clock)
10 Execution timed out 60 ms 18460 KB Time limit exceeded (wall clock)
11 Execution timed out 91 ms 14880 KB Time limit exceeded (wall clock)
12 Execution timed out 8010 ms 16164 KB Time limit exceeded
13 Execution timed out 8061 ms 16380 KB Time limit exceeded
14 Execution timed out 8015 ms 19908 KB Time limit exceeded
15 Execution timed out 8036 ms 19368 KB Time limit exceeded
16 Execution timed out 8087 ms 23052 KB Time limit exceeded
17 Execution timed out 8042 ms 26064 KB Time limit exceeded