oj.uz

Submission #475265

# Submission time Handle Problem Language Result Execution time Memory
475265 2021-09-21T17:09:34 Z Deepesson Regions (IOI09_regions) C++17
30 / 100
 8000 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 = SQRTN;///Mudar para SQRTN!!!!!!
int curg=0;
namespace big {
    int bucket[SQRTN][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];
    }
}
namespace small {
    std::map<int,int> 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){
            auto it = tab[pos].find(k);
            if(it==tab[pos].end())return 0;
            return it->second;
        }
        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][array[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);
    }
    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;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 63424 KB Output is correct
2 Correct 82 ms 63420 KB Output is correct
3 Correct 87 ms 63520 KB Output is correct
4 Correct 89 ms 63424 KB Output is correct
5 Correct 101 ms 63612 KB Output is correct
6 Correct 107 ms 63828 KB Output is correct
7 Correct 134 ms 63992 KB Output is correct
8 Correct 134 ms 64320 KB Output is correct
9 Correct 216 ms 65856 KB Output is correct
10 Correct 255 ms 67772 KB Output is correct
11 Correct 529 ms 69440 KB Output is correct
12 Correct 919 ms 72380 KB Output is correct
13 Correct 781 ms 73432 KB Output is correct
14 Correct 1783 ms 74764 KB Output is correct
15 Correct 4415 ms 81504 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8073 ms 88180 KB Time limit exceeded
2 Execution timed out 8074 ms 89112 KB Time limit exceeded
3 Execution timed out 8055 ms 96460 KB Time limit exceeded
4 Correct 1766 ms 78824 KB Output is correct
5 Correct 2829 ms 83584 KB Output is correct
6 Correct 991 ms 91308 KB Output is correct
7 Execution timed out 8028 ms 104672 KB Time limit exceeded
8 Execution timed out 8068 ms 121772 KB Time limit exceeded
9 Runtime error 394 ms 131076 KB Execution killed with signal 9
10 Runtime error 550 ms 131076 KB Execution killed with signal 9
11 Runtime error 411 ms 131076 KB Execution killed with signal 9
12 Runtime error 416 ms 131076 KB Execution killed with signal 9
13 Runtime error 394 ms 131076 KB Execution killed with signal 9
14 Runtime error 465 ms 131076 KB Execution killed with signal 9
15 Runtime error 389 ms 131076 KB Execution killed with signal 9
16 Runtime error 371 ms 131076 KB Execution killed with signal 9
17 Runtime error 468 ms 131076 KB Execution killed with signal 9