oj.uz

답안 #735643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735643 2023-05-04T12:28:42 Z Ahmed57 Regions (IOI09_regions) C++14
45 / 100
 8000 ms 131072 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= 100;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 4 ms 4944 KB Output is correct
3 Correct 5 ms 4944 KB Output is correct
4 Correct 8 ms 4944 KB Output is correct
5 Correct 12 ms 4944 KB Output is correct
6 Correct 20 ms 5072 KB Output is correct
7 Correct 33 ms 5072 KB Output is correct
8 Correct 34 ms 5072 KB Output is correct
9 Correct 51 ms 5456 KB Output is correct
10 Correct 89 ms 5584 KB Output is correct
11 Correct 144 ms 5968 KB Output is correct
12 Correct 146 ms 6496 KB Output is correct
13 Correct 160 ms 6268 KB Output is correct
14 Correct 566 ms 7644 KB Output is correct
15 Correct 678 ms 9612 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1970 ms 10976 KB Output is correct
2 Correct 1955 ms 10276 KB Output is correct
3 Correct 3219 ms 13860 KB Output is correct
4 Correct 2287 ms 14536 KB Output is correct
5 Correct 1388 ms 12828 KB Output is correct
6 Correct 7830 ms 15728 KB Output is correct
7 Execution timed out 8009 ms 25568 KB Time limit exceeded
8 Execution timed out 8016 ms 47868 KB Time limit exceeded
9 Execution timed out 8090 ms 94132 KB Time limit exceeded
10 Runtime error 6260 ms 131072 KB Execution killed with signal 9
11 Runtime error 7638 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8080 ms 97092 KB Time limit exceeded
13 Execution timed out 8058 ms 95976 KB Time limit exceeded
14 Execution timed out 8019 ms 102544 KB Time limit exceeded
15 Execution timed out 8031 ms 126452 KB Time limit exceeded
16 Execution timed out 8034 ms 123652 KB Time limit exceeded
17 Execution timed out 8103 ms 109496 KB Time limit exceeded