Submission #1292092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292092		qrn	Regions (IOI09_regions)	C++20	15 / 100	425 ms	196608 KiB

regions

// ome47
// booooooo
#include "bits/stdc++.h"
using namespace std;
#define intt long long

const intt mxN = 2e5 + 5;
const intt LG = 20;
const intt inf = 1e18;

intt n, r, q, timer;
vector<vector<intt>> graph, pre, boo;
vector<intt> h(mxN), par(mxN), in(mxN), subsize(mxN);

void dfs(intt node, intt parent) {
    in[node] = timer++;
    subsize[node] = 1;
    for(auto u : graph[node]) {
        if(u != parent) {
            dfs(u, node);
            subsize[node] += subsize[u];
        }
    }
}

bool cmp(intt &a, intt &b) {
    return in[a] < in[b];
}

void _() {
    cin >> n >> r >> q;
    graph.assign(n + 1, vector<intt> {});
    pre.assign(r + 1, vector<intt>(n + 1, 0ll));
    boo.assign(r + 1, vector<intt>(r + 1, 0ll));

    for(intt i = 1; i <= n; i++) {
        intt supervisor, race;
        if(i == 1) {
            cin >> race;
        } else {
            cin >> supervisor >> race;
            graph[supervisor].push_back(i);
            graph[i].push_back(supervisor);
        }
        h[i] = race;
    }
    dfs(1, 1);

    vector<intt> v;
    for(intt i = 0; i < n; i++) v.push_back(i + 1);
    sort(v.begin(), v.end(), cmp);

    vector<intt> node_v = v;
    for(intt i = 0; i < n; i++) v[i] = h[v[i]];

    pre[v[0]][0]=1;
    for(intt i = 1; i < n; i++) {
        for(intt j = 1; j <= r; j++) {
            pre[j][i] += pre[j][i-1];
        }
        pre[v[i]][i]++;
    }

    for(intt i = 0; i < n; i++) {
        intt lidx = i, ridx = i + subsize[node_v[i]] - 1;
        for(intt j = 1; j <= r; j++) {
            if(i == 0) {
                boo[v[i]][j] += pre[j][ridx];
            } else {
                boo[v[i]][j] += (pre[j][ridx] - pre[j][lidx-1]);
            }
        }
    }

    while(q--) {
        intt a, b;
        cin >> a >> b;
        cout << boo[a][b] << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1;
    // cin >> t;
    while(t--){
        // cout << endl;
        _();
    }
}
// ⠀⠀⠀⠀⠀⠀⠀⢀⣤⣦⣶⣤⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣤⢀⣀⡀⣠⣄⣠⣶⣿⣿⣿⣿⣿⣿⣿⣷⣾⡦⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠻⡳⢛⠛⠒⠚⢛⣿⣿⠟⠋⠉⠛⠛⢿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀
// ⢛⡛⢿⣿⠟⠻⠛⣿⣇⣶⣖⣤⣀⣄⡰⣹⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀
// ⢿⠿⠿⠿⠿⠿⠿⢭⣐⠠⢼⣬⠽⢈⢁⡿⠛⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣛⣱⣤⣤⣤⣀⣄⣄⣗⢌⠋⠉⢙⣴⣧⢤⣤⣤⣤⣦⡀⠀⠀⠀⠀⢺⡿
// ⣿⣿⣿⠟⠛⠋⠀⡬⠼⢠⠍⠂⠀⠨⡇⠀⡏⠉⠛⢿⣧⠀⠀⠀⠀⢸⣀
// ⣟⠄⠀⠀⠀⠀⠀⢡⠀⠀⠀⠀⠀⡠⠁⢀⠁⠀⠀⠀⠘⣗⢀⠄⢶⣼⣾
// ⠀⠀⠀⢠⣦⠇⠀⠀⠁⠒⠒⠒⠈⠀⠀⠀⣞⢶⡀⠀⠀⠹⣧⣠⡞⣸⣏
// ⠀⠀⢀⡞⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣦⡀⠀⠈⠫⣕⣻⡇
// ⠀⠀⣾⣧⠈⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⣿⣿⣿⣷⣦⡠⡤⠀⣿⡇
// ⠠⢿⣿⣿⠂⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠴⣿⣿⣿⣿⠟⠋⢀⣤⣿⣷
// ⣀⣀⣀⣙⣃⣠⣤⣔⣤⣢⣵⣒⣒⣢⣄⣤⣄⣛⣋⣉⣀⣀⣤⣿⣿⣿⣿

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