제출 #475289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475289		Deepesson	Regions (IOI09_regions)	C++17	100 / 100	6928 ms	126596 KiB

regions

#include <bits/stdc++.h>
#define MAXN 205000
#define REGIOES 25100
#define INI MAXN-5
#define SQRTN 450
int cores[MAXN],array[MAXN],primeiro[MAXN],size[MAXN],cur;
std::vector<int> con[MAXN];
std::vector<int> indices[REGIOES];
int N,R,Q;
int dfs(int pos,int prev){
    array[cur]=cores[pos];
    primeiro[pos]=cur;
    ++cur;
    int res=1;
    for(auto&x:con[pos]){
        if(x==prev)continue;
        res+=dfs(x,pos);
    }
    return size[pos]=res;
}
int tamanho[REGIOES];
bool grandes[REGIOES];
int indicegrandeza[REGIOES];
const int threshold = 167;///Mudar para SQRTN!!!!!!
int slots = 550;
int curg=0;
namespace big {
    int bucket[555][REGIOES];
    int tab[MAXN*4];
    void query(int l,int r,int la=0,int ra=INI,int pos=1){
        if(ra<l||la>r)return;
        if(la>=l&&ra<=r){
            ++tab[pos];
            return;
        }
        int m=(la+ra)/2;
        query(l,r,la,m,pos*2);
        query(l,r,m+1,ra,(pos*2)+1);
    }
    void build(int k,int la=0,int ra=INI,int pos=1){
        if(tab[pos]){
            for(int i=la;i!=ra+1;++i){
                bucket[k][array[i]]+=tab[pos];
            }
            tab[pos]=0;
        }
        if(la==ra)return;
        int m=(la+ra)/2;
        build(k,la,m,pos*2);
        build(k,m+1,ra,(pos*2)+1);
    }
    void preparar(void){
        for(int i=0;i!=REGIOES;++i){
            if(grandes[i]){
                for(auto&x:indices[i]){
                    query(primeiro[x],primeiro[x]+size[x]-1);
                }
                build(indicegrandeza[i]);
            }
        }
    }
    int consulta(int x,int y){
        return bucket[indicegrandeza[x]][y];
    }
}
typedef std::pair<int,int> pii;
namespace small {
    pii* tab[MAXN*4];
    int query(int l,int r,int k,int la=0,int ra=INI,int pos=1){
        if(ra<l||la>r)return 0;
        if(la>=l&&ra<=r){
            int l=0,r=ra-la;
            while(l<r){
                int m = (l+r)/2;
                if(tab[pos][m].first>=k){
                    r=m;
                }else l=m+1;
            }
            if(tab[pos][l].first==k)return tab[pos][l].second;return 0;
        }
        int m=(la+ra)/2;
        return query(l,r,k,la,m,pos*2) +
        query(l,r,k,m+1,ra,(pos*2)+1);
    }
    void build(int la=0,int ra=INI,int pos=1){
        tab[pos]=(pii*)malloc((ra-la+1)*sizeof(pii));
        for(int i=la;i!=ra+1;++i){
            tab[pos][i-la]={array[i],1};
        }
        std::sort(&tab[pos][0],&tab[pos][ra-la+1]);
        {
            std::vector<pii> novo_vetor;
            for(int i=0;i!=(ra-la+1);++i){
                if(!novo_vetor.size()||novo_vetor.back().first!=tab[pos][i].first){
                    novo_vetor.push_back(tab[pos][i]);
                }else ++novo_vetor.back().second;
            }
            for(int i=0;i!=(ra-la+1);++i)tab[pos][i]={1e9,0};
            for(int i=0;i!=novo_vetor.size();++i) tab[pos][i]=novo_vetor[i];
        }
        if(la==ra)return;
        int m=(la+ra)/2;
        build(la,m,pos*2);
        build(m+1,ra,(pos*2)+1);
    }
    int consulta(int a,int b){
        int res=0;
        for(auto&x:indices[a]){
            res+=query(primeiro[x],primeiro[x]+size[x]-1,b);
        }
        return res;
    }
};
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin>>N>>R>>Q;
    std::cin>>cores[0];
    indices[cores[0]].push_back(0);
    for(int i=1;i!=N;++i){
        int a,b;std::cin>>a>>b;--a;
        cores[i]=b;
        indices[b].push_back(i);
        tamanho[b]++;
        con[a].push_back(i);con[i].push_back(a);
    }
    std::vector<pii> tamanhos;

    for(int i=0;i!=REGIOES;++i){
        if(tamanho[i]>=1){
            tamanhos.push_back({tamanho[i],i});
        }
    }
    slots=std::min(slots,(int)tamanhos.size());
    std::sort(tamanhos.begin(),tamanhos.end(),std::greater<pii>());
    for(int i=0;i!=slots;++i){
        grandes[tamanhos[i].second]=true;
        indicegrandeza[tamanhos[i].second]=curg;curg++;
    }
    dfs(0,0);
    big::preparar();
    small::build();
    for(int i=0;i!=Q;++i){
        int a,b;
        std::cin>>a>>b;
        if(grandes[a]){
            std::cout<<big::consulta(a,b)<<std::endl;
        }else {
            std::cout<<small::consulta(a,b)<<std::endl;
        }
    }
}

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

regions.cpp: In function 'int small::query(int, int, int, int, int, int)':
regions.cpp:79:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   79 |             if(tab[pos][l].first==k)return tab[pos][l].second;return 0;
      |             ^~
regions.cpp:79:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   79 |             if(tab[pos][l].first==k)return tab[pos][l].second;return 0;
      |                                                               ^~~~~~
regions.cpp: In function 'void small::build(int, int, int)':
regions.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for(int i=0;i!=novo_vetor.size();++i) tab[pos][i]=novo_vetor[i];
      |                         ~^~~~~~~~~~~~~~~~~~~

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