#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 = 500;
int curg=0;
namespace big {
int bucket[505][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 |
106 ms |
47248 KB |
Output is correct |
| 2 |
Correct |
109 ms |
47292 KB |
Output is correct |
| 3 |
Correct |
128 ms |
47328 KB |
Output is correct |
| 4 |
Correct |
146 ms |
47492 KB |
Output is correct |
| 5 |
Correct |
164 ms |
47484 KB |
Output is correct |
| 6 |
Correct |
400 ms |
48728 KB |
Output is correct |
| 7 |
Correct |
325 ms |
48240 KB |
Output is correct |
| 8 |
Correct |
380 ms |
48416 KB |
Output is correct |
| 9 |
Correct |
516 ms |
49508 KB |
Output is correct |
| 10 |
Correct |
690 ms |
50560 KB |
Output is correct |
| 11 |
Correct |
552 ms |
49716 KB |
Output is correct |
| 12 |
Correct |
830 ms |
51696 KB |
Output is correct |
| 13 |
Correct |
674 ms |
50808 KB |
Output is correct |
| 14 |
Correct |
538 ms |
50288 KB |
Output is correct |
| 15 |
Correct |
743 ms |
53616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1298 ms |
53868 KB |
Output is correct |
| 2 |
Correct |
1454 ms |
53676 KB |
Output is correct |
| 3 |
Correct |
1989 ms |
56496 KB |
Output is correct |
| 4 |
Correct |
1130 ms |
59356 KB |
Output is correct |
| 5 |
Correct |
1482 ms |
63200 KB |
Output is correct |
| 6 |
Correct |
1564 ms |
66848 KB |
Output is correct |
| 7 |
Correct |
1756 ms |
73876 KB |
Output is correct |
| 8 |
Correct |
2743 ms |
80048 KB |
Output is correct |
| 9 |
Correct |
5952 ms |
89888 KB |
Output is correct |
| 10 |
Execution timed out |
8058 ms |
113572 KB |
Time limit exceeded |
| 11 |
Execution timed out |
8029 ms |
110180 KB |
Time limit exceeded |
| 12 |
Correct |
3162 ms |
93292 KB |
Output is correct |
| 13 |
Correct |
5274 ms |
94424 KB |
Output is correct |
| 14 |
Correct |
3824 ms |
102140 KB |
Output is correct |
| 15 |
Execution timed out |
8077 ms |
114052 KB |
Time limit exceeded |
| 16 |
Correct |
4334 ms |
121660 KB |
Output is correct |
| 17 |
Correct |
5827 ms |
111944 KB |
Output is correct |
