Submission #475280

# Submission time Handle Problem Language Result Execution time Memory
475280 2021-09-21T18:00:33 Z Deepesson Regions (IOI09_regions) C++17
25 / 100
8000 ms 91788 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 = 1100;
int curg=0;
namespace big {
    int bucket[1201][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 {
    std::vector<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=tab[pos].size()-1;
            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){
        for(int i=la;i!=ra+1;++i){
            tab[pos].push_back({array[i],1});
        }
        std::sort(tab[pos].begin(),tab[pos].end());
        {
            std::vector<pii> novo_vetor;
            for(auto&x:tab[pos]){
                if(!novo_vetor.size()||novo_vetor.back().first!=x.first){
                    novo_vetor.push_back(x);
                }else ++novo_vetor.back().second;
            }
            tab[pos]=novo_vetor;
        }
        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;
    slots=std::min(slots,(int)tamanhos.size());
    for(int i=0;i!=REGIOES;++i){
        if(tamanho[i]>=1){
            tamanhos.push_back({tamanho[i],i});
        }
    }
    std::sort(tamanhos.begin(),tamanhos.end(),std::greater<pii>());
    for(int i=0;i!=slots;++i){
        grandes[tamanhos[i].second]=true;
    }
    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;
      |                                                               ^~~~~~
# Verdict Execution time Memory Grader output
1 Correct 207 ms 68792 KB Output is correct
2 Correct 205 ms 68912 KB Output is correct
3 Correct 210 ms 68856 KB Output is correct
4 Correct 209 ms 68884 KB Output is correct
5 Correct 215 ms 68912 KB Output is correct
6 Correct 233 ms 68912 KB Output is correct
7 Correct 260 ms 69100 KB Output is correct
8 Correct 260 ms 69056 KB Output is correct
9 Correct 307 ms 69604 KB Output is correct
10 Correct 384 ms 69436 KB Output is correct
11 Correct 576 ms 69804 KB Output is correct
12 Correct 716 ms 70228 KB Output is correct
13 Correct 694 ms 70200 KB Output is correct
14 Correct 1223 ms 70472 KB Output is correct
15 Correct 2698 ms 73496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 8063 ms 73632 KB Time limit exceeded
2 Execution timed out 8048 ms 73260 KB Time limit exceeded
3 Execution timed out 8051 ms 75688 KB Time limit exceeded
4 Correct 1258 ms 70704 KB Output is correct
5 Correct 1763 ms 72492 KB Output is correct
6 Execution timed out 8042 ms 72108 KB Time limit exceeded
7 Execution timed out 8096 ms 73048 KB Time limit exceeded
8 Execution timed out 8084 ms 78684 KB Time limit exceeded
9 Execution timed out 8035 ms 78508 KB Time limit exceeded
10 Execution timed out 8015 ms 84232 KB Time limit exceeded
11 Execution timed out 8084 ms 80564 KB Time limit exceeded
12 Execution timed out 8067 ms 79452 KB Time limit exceeded
13 Execution timed out 8076 ms 80340 KB Time limit exceeded
14 Execution timed out 8101 ms 80380 KB Time limit exceeded
15 Execution timed out 8099 ms 84404 KB Time limit exceeded
16 Execution timed out 8064 ms 91788 KB Time limit exceeded
17 Execution timed out 8042 ms 90192 KB Time limit exceeded