Submission #249802

#	Time	Username	Problem	Language	Result	Execution time	Memory
249802		Uzumaki_Naturoo	Regions (IOI09_regions)	C++14	100 / 100	3952 ms	51320 KiB

regions

/// 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 (stderr)

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 / 15
• Subtask 2: 85 / 85