Submission #1326366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326366		adiyer	Regions (IOI09_regions)	C++20	4 / 100	4303 ms	186144 KiB

regions

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 3;
const int B = 450;
const int REG = 25002;

ll k;

int n, m, q, tick;
int a[N], p[N], tin[N], tout[N], pos[N], down[N / B + 3][REG];

short int cnt[N / B + 3][REG];

vector < int > g[N];
vector < short int > d[REG];

void dfs(int v){
    tin[v] = ++tick, pos[tick] = v;
    for(int u : g[v]) dfs(u);
    tout[v] = tick;
}

void dfs2(int v, int tp){
    if((tin[v] + B - 1) / B != tp) down[tp][a[v]]++;
    for(int u : g[v]) dfs2(u, tp);
}

int calc(vector < short int > &v, int x){
    int l = -1, r = v.size();
    while(r - l > 1){
        int md = (l + r) / 2;
        if(v[md] <= x) l = md;
        else r = md;
    }
    return r;
}

void solve(){
    cin >> n >> m >> q >> a[1];
    for(int i = 2; i <= n; i++) cin >> p[i] >> a[i], g[p[i]].push_back(i);
    dfs(1);
    for(int i = 1; i <= n; i++) cnt[(i + B - 1) / B][a[pos[i]]]++;
    for(int i = 1; i <= (n + B - 1) / B; i++) dfs2(pos[(i - 1) * B + 1], i);
    for(int x = 1; x <= (n + B - 1) / B; x++){
        for(int i = (x - 1) * B + 1; i < x * B && i <= n; i++){
            for(int j = (x - 1) * B + 1; j < x * B && j <= n; j++){
                if(i == j || tin[i] > tin[j] || tout[i] < tout[j]) continue;
                d[a[i]].push_back(a[j]);
            }   
        }
    }
    for(int i = 1; i <= m; i++){
        sort(d[i].begin(), d[i].end());
    }
    while(q--){
        int r1, r2;
        cin >> r1 >> r2, k = 0;
        for(int i = 1; i <= (n + B - 1) / B; i++) k += cnt[i][r1] * 1ll * down[i][r2];
        cout << k + calc(d[r1], r2) - calc(d[r1], r2 - 1) << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

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