oj.uz

답안 #735672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735672 2023-05-04T12:50:17 Z Ahmed57 Regions (IOI09_regions) C++14
45 / 100
 8000 ms 23180 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;
}
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(){
    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<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: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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4988 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 6 ms 4944 KB Output is correct
4 Correct 8 ms 4944 KB Output is correct
5 Correct 15 ms 5016 KB Output is correct
6 Correct 17 ms 5072 KB Output is correct
7 Correct 40 ms 5072 KB Output is correct
8 Correct 34 ms 5072 KB Output is correct
9 Correct 60 ms 5456 KB Output is correct
10 Correct 106 ms 5524 KB Output is correct
11 Correct 143 ms 5700 KB Output is correct
12 Correct 199 ms 6096 KB Output is correct
13 Correct 184 ms 5804 KB Output is correct
14 Correct 302 ms 6404 KB Output is correct
15 Correct 371 ms 8144 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 256 ms 8980 KB Time limit exceeded (wall clock)
2 Execution timed out 347 ms 8000 KB Time limit exceeded (wall clock)
3 Execution timed out 374 ms 10400 KB Time limit exceeded (wall clock)
4 Correct 400 ms 6712 KB Output is correct
5 Correct 439 ms 7988 KB Output is correct
6 Execution timed out 2150 ms 9324 KB Time limit exceeded (wall clock)
7 Correct 2188 ms 8980 KB Output is correct
8 Execution timed out 592 ms 13072 KB Time limit exceeded (wall clock)
9 Correct 3947 ms 13732 KB Output is correct
10 Correct 6181 ms 17788 KB Output is correct
11 Correct 6579 ms 14048 KB Output is correct
12 Execution timed out 8080 ms 15724 KB Time limit exceeded
13 Execution timed out 8090 ms 15300 KB Time limit exceeded
14 Execution timed out 8080 ms 16992 KB Time limit exceeded
15 Execution timed out 8074 ms 18484 KB Time limit exceeded
16 Execution timed out 8032 ms 22060 KB Time limit exceeded
17 Execution timed out 8009 ms 23180 KB Time limit exceeded