Submission #475289

# Submission time Handle Problem Language Result Execution time Memory
475289 2021-09-21T18:21:42 Z Deepesson Regions (IOI09_regions) C++17
100 / 100
6928 ms 126596 KB
#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;
        }
    }
}

Compilation message

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];
      |                         ~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 110 ms 47400 KB Output is correct
2 Correct 112 ms 47296 KB Output is correct
3 Correct 125 ms 47432 KB Output is correct
4 Correct 169 ms 47464 KB Output is correct
5 Correct 172 ms 47568 KB Output is correct
6 Correct 412 ms 48640 KB Output is correct
7 Correct 315 ms 48236 KB Output is correct
8 Correct 378 ms 48548 KB Output is correct
9 Correct 525 ms 49592 KB Output is correct
10 Correct 670 ms 50484 KB Output is correct
11 Correct 556 ms 49740 KB Output is correct
12 Correct 821 ms 51580 KB Output is correct
13 Correct 738 ms 50876 KB Output is correct
14 Correct 574 ms 50292 KB Output is correct
15 Correct 672 ms 53644 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1228 ms 53856 KB Output is correct
2 Correct 1426 ms 53684 KB Output is correct
3 Correct 2170 ms 56532 KB Output is correct
4 Correct 1173 ms 60512 KB Output is correct
5 Correct 1379 ms 64448 KB Output is correct
6 Correct 1678 ms 68396 KB Output is correct
7 Correct 1951 ms 76256 KB Output is correct
8 Correct 2854 ms 82064 KB Output is correct
9 Correct 5144 ms 93176 KB Output is correct
10 Correct 6056 ms 118484 KB Output is correct
11 Correct 6873 ms 115168 KB Output is correct
12 Correct 3004 ms 96580 KB Output is correct
13 Correct 4496 ms 97620 KB Output is correct
14 Correct 3559 ms 106192 KB Output is correct
15 Correct 6928 ms 119056 KB Output is correct
16 Correct 4505 ms 126596 KB Output is correct
17 Correct 4852 ms 116300 KB Output is correct