oj.uz

Submission #249802

# Submission time Handle Problem Language Result Execution time Memory
249802 2020-07-15T18:28:23 Z Uzumaki_Naturoo Regions (IOI09_regions) C++14
100 / 100
 3952 ms 51320 KB 
/// You just can't beat the person who never gives up
/// ICPC next year

///#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 2e5+5 ;

int n ,r ,q ,u ,v ,colr[N] ,id[N] ,idx ,cur_idx ;
vector<int> adj[N] ,colr_pos[N] ;
vector<pair<int,int>> colr_range[N] ;
long long cur_cnt[505][N]  ;
void dfs(int p,int gp){
    int s = cur_idx++ ;
    colr_pos[colr[p]].push_back(s) ;
    for(int ch:adj[p]) if(ch!=gp) dfs(ch,p) ;
    int e = cur_idx++ ;
    colr_range[colr[p]].push_back({s,e}) ;
}
int upi ;
void solve(int ii,int p,int gp){
    if(colr[p]==ii) ++upi ;
    cur_cnt[id[ii]][colr[p]] += upi ;
    for(int ch:adj[p]) if(ch!=gp) solve(ii,ch,p) ;
    if(colr[p]==ii) --upi ;
}
bool Never_give_up(){
    cin >> n >> r >> q ;
    cin >> colr[1] ;
    for(int i=2;i<=n;++i){
        cin >> v >> colr[i] ;
        adj[i].push_back(v);
        adj[v].push_back(i);
    }
    dfs(1,1) ;
    int sqr = sqrt(n) ;
    for(int i=1;i<=n;++i){
        if(colr_range[i].size()<sqr) continue ;
        if(!id[i]) id[i] = ++idx ;
        upi = 0 ;
        solve(i,1,1);
    }
    while(q--){
        cin >> u >> v ;
        if(colr_range[u].size()>=sqr){
            cout << cur_cnt[id[u]][v] << endl ;
            continue ;
        }
        else{
            long long ans = 0 ;
            for(auto lr:colr_range[u]){
                int l = lr.first ;
                int r = lr.second ;
                ans += upper_bound(colr_pos[v].begin(),colr_pos[v].end(),r) - lower_bound(colr_pos[v].begin(),colr_pos[v].end(),l) ;
            }
            cout << ans << endl ;
        }
    }
    return 0;
}
int main(){
/*#ifndef ONLINE_JUDGE
    freopen("input.txt" ,"r" ,stdin);
    freopen("output.txt" ,"w" ,stdout);
#endif*/
    std::ios::sync_with_stdio(0);
    cin.tie(0) ,cout.tie(0);
    int t = 1 ;
    //cin >> t ;
    while(t--){
        Never_give_up();
    }
    return 0;
}

Compilation message

regions.cpp: In function 'bool Never_give_up()':
regions.cpp:40:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(colr_range[i].size()<sqr) continue ;
            ~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:47:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(colr_range[u].size()>=sqr){
            ~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 14 ms 14464 KB Output is correct
6 Correct 25 ms 14592 KB Output is correct
7 Correct 33 ms 14592 KB Output is correct
8 Correct 38 ms 14712 KB Output is correct
9 Correct 62 ms 15104 KB Output is correct
10 Correct 100 ms 15096 KB Output is correct
11 Correct 115 ms 15232 KB Output is correct
12 Correct 167 ms 15872 KB Output is correct
13 Correct 168 ms 15872 KB Output is correct
14 Correct 254 ms 16128 KB Output is correct
15 Correct 249 ms 19832 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1742 ms 19728 KB Output is correct
2 Correct 1990 ms 18936 KB Output is correct
3 Correct 2915 ms 21880 KB Output is correct
4 Correct 317 ms 16248 KB Output is correct
5 Correct 358 ms 18432 KB Output is correct
6 Correct 592 ms 21484 KB Output is correct
7 Correct 1167 ms 23160 KB Output is correct
8 Correct 1189 ms 33656 KB Output is correct
9 Correct 2091 ms 24572 KB Output is correct
10 Correct 2927 ms 51320 KB Output is correct
11 Correct 3952 ms 26228 KB Output is correct
12 Correct 1319 ms 25080 KB Output is correct
13 Correct 1952 ms 26364 KB Output is correct
14 Correct 2709 ms 29500 KB Output is correct
15 Correct 2683 ms 31364 KB Output is correct
16 Correct 2883 ms 40320 KB Output is correct
17 Correct 2584 ms 42104 KB Output is correct