oj.uz

Submission #475262

# Submission time Handle Problem Language Result Execution time Memory
475262 2021-09-21T17:05:59 Z Deepesson Regions (IOI09_regions) C++17
25 / 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::unordered_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 210 ms 108332 KB Output is correct
2 Correct 209 ms 108368 KB Output is correct
3 Correct 209 ms 108352 KB Output is correct
4 Correct 216 ms 108380 KB Output is correct
5 Correct 217 ms 108480 KB Output is correct
6 Correct 233 ms 108724 KB Output is correct
7 Correct 260 ms 108816 KB Output is correct
8 Correct 263 ms 109040 KB Output is correct
9 Correct 322 ms 110400 KB Output is correct
10 Correct 385 ms 111936 KB Output is correct
11 Correct 620 ms 113308 KB Output is correct
12 Correct 779 ms 115792 KB Output is correct
13 Correct 817 ms 116512 KB Output is correct
14 Correct 1577 ms 117660 KB Output is correct
15 Correct 2874 ms 123544 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8036 ms 128888 KB Time limit exceeded
2 Execution timed out 8083 ms 129472 KB Time limit exceeded
3 Runtime error 269 ms 131076 KB Execution killed with signal 9
4 Correct 1839 ms 121208 KB Output is correct
5 Correct 2166 ms 125532 KB Output is correct
6 Runtime error 341 ms 131076 KB Execution killed with signal 9
7 Runtime error 259 ms 131076 KB Execution killed with signal 9
8 Runtime error 480 ms 131076 KB Execution killed with signal 9
9 Runtime error 257 ms 131076 KB Execution killed with signal 9
10 Runtime error 431 ms 131076 KB Execution killed with signal 9
11 Runtime error 297 ms 131076 KB Execution killed with signal 9
12 Runtime error 301 ms 131076 KB Execution killed with signal 9
13 Runtime error 308 ms 131076 KB Execution killed with signal 9
14 Runtime error 356 ms 131076 KB Execution killed with signal 9
15 Runtime error 281 ms 131076 KB Execution killed with signal 9
16 Runtime error 274 ms 131076 KB Execution killed with signal 9
17 Runtime error 363 ms 131076 KB Execution killed with signal 9