oj.uz

답안 #475275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475275 2021-09-21T17:29:59 Z Deepesson Regions (IOI09_regions) C++17
75 / 100
 7964 ms 131076 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 = 150;///Mudar para SQRTN!!!!!!
int curg=0;
namespace big {
    int bucket[1340][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<short,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);
    }
    dfs(0,0);
    for(int i=0;i!=REGIOES;++i){
        if(tamanho[i]>threshold){
            indicegrandeza[i]=curg;
            ++curg;
            grandes[i]=true;
        }
    }
    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:78:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |             if(tab[pos][l].first==k)return tab[pos][l].second;return 0;
      |             ^~
regions.cpp:78:63: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |             if(tab[pos][l].first==k)return tab[pos][l].second;return 0;
      |                                                               ^~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 68920 KB Output is correct
2 Correct 205 ms 68880 KB Output is correct
3 Correct 213 ms 68848 KB Output is correct
4 Correct 213 ms 68944 KB Output is correct
5 Correct 217 ms 68912 KB Output is correct
6 Correct 233 ms 68916 KB Output is correct
7 Correct 262 ms 69096 KB Output is correct
8 Correct 263 ms 69004 KB Output is correct
9 Correct 323 ms 69424 KB Output is correct
10 Correct 358 ms 69452 KB Output is correct
11 Correct 595 ms 69700 KB Output is correct
12 Correct 747 ms 70188 KB Output is correct
13 Correct 683 ms 70204 KB Output is correct
14 Correct 949 ms 71324 KB Output is correct
15 Correct 1016 ms 75032 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1541 ms 75480 KB Output is correct
2 Correct 1339 ms 75076 KB Output is correct
3 Correct 2179 ms 78156 KB Output is correct
4 Correct 981 ms 72120 KB Output is correct
5 Correct 1721 ms 72496 KB Output is correct
6 Correct 1129 ms 74532 KB Output is correct
7 Correct 2964 ms 77100 KB Output is correct
8 Correct 5420 ms 83964 KB Output is correct
9 Correct 7964 ms 101280 KB Output is correct
10 Runtime error 2278 ms 131076 KB Execution killed with signal 9
11 Runtime error 1689 ms 131076 KB Execution killed with signal 9
12 Correct 2627 ms 121460 KB Output is correct
13 Correct 3367 ms 122532 KB Output is correct
14 Correct 3537 ms 125364 KB Output is correct
15 Runtime error 2301 ms 131076 KB Execution killed with signal 9
16 Runtime error 2233 ms 131076 KB Execution killed with signal 9
17 Runtime error 2279 ms 131076 KB Execution killed with signal 9