제출 #415752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415752		Antekb	Regions (IOI09_regions)	C++14	100 / 100	4951 ms	130604 KiB

regions

#include<bits/stdc++.h>
using namespace std;
const int N=500, M=25000, K=200000;
vector<int> E[K];
int R[K], pre[K], post[K], ile3[M], sta[M], sta2[M];
vector<int> pocz[M], kon[M];
int ile[M][N], ile2[M][N], gdzie[M];
vector<int> duz;
int wsk=0;
void dfs(int v){
    //cout<<v<<"q\n";
    pre[v]=wsk++;
    pocz[R[v]].push_back(pre[v]);
    sta[R[v]]++;
    sta2[R[v]]++;
    for(int i=0; i<duz.size(); i++){
        ile[R[v]][i]-=sta[duz[i]];
        ile2[R[v]][i]+=sta2[duz[i]];
    }
    for(int u:E[v]){
        dfs(u);
    }
    for(int i=0; i<duz.size(); i++){
        ile[R[v]][i]+=sta[duz[i]];
    }
    sta2[R[v]]--;
    post[v]=wsk;
    kon[R[v]].push_back(post[v]);
}
int main(){
    int n, r, q;
    cin>>n>>r>>q;
    for(int i=0; i<n ;i++){
        int h, p;
        if(i){
            cin>>p;
            p--;
            E[p].push_back(i);
        }
        cin>>R[i];
        --R[i];

        ile3[R[i]]++;
    }
    for(int i=0; i<r; i++){
        if(ile3[i]>=N){
            duz.push_back(i);
            gdzie[i]=duz.size();
        }
    }
    dfs(0);
    for(int i=0;i<q; i++){
        int r1, r2;
        cin>>r1>>r2;
        r1--;
        r2--;
        if(gdzie[r1]){
            cout<<ile2[r2][gdzie[r1]-1];
        }
        else if(gdzie[r2]){
            cout<<ile[r1][gdzie[r2]-1];
        }
        else{
                //cout<<"a";
            int ans=0;
            for(int i=0; i<pocz[r1].size(); i++){
               // cout<<"b";
                ans+=(lower_bound(pocz[r2].begin(), pocz[r2].end(), kon[r1][i])-lower_bound(pocz[r2].begin(), pocz[r2].end(), pocz[r1][i]));
            }
            cout<<ans;
        }
        cout<<endl;
    }
}

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

regions.cpp: In function 'void dfs(int)':
regions.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0; i<duz.size(); i++){
      |                  ~^~~~~~~~~~~
regions.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0; i<duz.size(); i++){
      |                  ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:34:13: warning: unused variable 'h' [-Wunused-variable]
   34 |         int h, p;
      |             ^
regions.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=0; i<pocz[r1].size(); i++){
      |                          ~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85