Submission #738096

#	Time	Username	Problem	Language	Result	Execution time	Memory
738096		nonono	Regions (IOI09_regions)	C++14	0 / 100	644 ms	130448 KiB

regions

#include "bits/stdc++.h"
using namespace std;

const int mxN = 2e5 + 10;
const int mxR = 25000 + 10;

int n, r, q, h[mxN];
vector<vector<int>> adj(mxN), a(mxR), b(mxR);
int pr[mxN];
unordered_map<int, int> sum[mxR];

int Time = 0, in[mxN], out[mxN], id[mxN];

void dfs(int u){
    in[u] = ++ Time;
    id[Time] = u;
    
    a[h[u]].push_back(u);
    b[h[u]].push_back(in[u]);
    
    for(int v : adj[u]){
        dfs(v);
    }
    
    out[u] = Time;
}

signed main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> r >> q;
    
    for(int i = 1; i <= n; i ++){
        if(i > 1){
            int par;
            cin >> par;
            adj[par].push_back(i);
        }
        
        cin >> h[i];
    }
    
    dfs(1);
    
    for(int i = 1; i <= r; i ++){
        if((int)a[i].size() <= (int)sqrt(n)) continue ;
        for(int j = 0; j <= n; j ++) pr[j] = 0;
        
        for(int x : a[i]){
            int L = in[x];
            int R = out[x];
            
            pr[L] ++ ;
            pr[R + 1] -- ;
        }
        
        for(int j = 1; j <= n; j ++){
            pr[j] += pr[j - 1];
            sum[i][h[id[j]]] += pr[j];
        }
    }
    
    while(q --){
        int x, y;
        cin >> x >> y;
        
        if((int)a[x].size() <= (int)sqrt(n)){
            int res = 0;
            
            for(int i : a[x]){
                int L = in[i];
                int R = out[i];
                
                int l = upper_bound(b[y].begin(), b[y].end(), L) - b[y].begin();
                int r = upper_bound(b[y].begin(), b[y].end(), R) - b[y].begin();
                
                res += max(r - l, 0);
            }
            
            cout << res << "\n";
        } else {
            
            cout << sum[x][y] << "\n";
        }
        
    }
    
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85