제출 #735664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735664		Ahmed57	Regions (IOI09_regions)	C++14	55 / 100	8102 ms	27224 KiB

regions

#pragma GCC optimize(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= 800;
    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);
        }
    }
    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[{a,b}]!=0){
                cout<<mp[{a,b}]-1<<endl;continue;
            }
            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<<endl;
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp:1:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
    1 | #pragma GCC optimize(Ofast)
      |                      ^~~~~
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 / 15
• Subtask 2: 40 / 85