Submission #1162323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162323		nh0902	Regions (IOI09_regions)	C++20	0 / 100	29 ms	14484 KiB

regions

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 200005;

const int R = 25005;

const long long inf = 1e13;

const long long mod = 1e9 + 7;

int n, r, m, q;

int h[N];

int cnt_r[R];

vector<int> g[N];

pair<int, int> query[N];

map<int, int> ans[R];

vector<int> query_down[R], query_up[R];

int cur_cnt[R];

int sz[N];

void predfs(int u) {
    sz[u] = 1;
    for (int v : g[u]) {
        predfs(v);
        sz[u] += sz[v];
    }
}

void update(int u, int val) {
    cur_cnt[h[u]] += val;
    for (int v : g[u]) update(v, val);
}

void dfs(int u) {

    if (sz[u] == 1) {
        cur_cnt[h[u]] ++;
        return;
    }
    int b = 0;
    for (int v : g[u]) {
        if (b == 0 || sz[b] < sz[v]) b = v;
    }

    for (int v : g[u]) if (v != b) {
        dfs(v);
        update(v, - 1);
    }

    dfs(b);

    for (int v : g[u]) if (v != b) {
        update(v, 1);
    }

    for (int x : query_down[h[u]]) {
        ans[h[u]][x] += cur_cnt[x];
    }

    cur_cnt[h[u]] ++;
}

void dfs2(int u) {
    for (int x : query_up[h[u]]) {
        ans[x][h[u]] += cur_cnt[x];
    }

    cur_cnt[h[u]] ++;

    for (int v : g[u]) dfs2(v);

    cur_cnt[h[u]] --;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Use standard input to read from "paint.in"
	//freopen("promote.in", "r", stdin);
	// Use standard output to write to "paint.out"
	//freopen("promote.out", "w", stdout);

    cin >> n >> r >> q;

    m = sqrt(n) + 1;

    //cout << m << "\n";

    cin >> h[1];
    cnt_r[h[1]] ++;

    int x;
    for (int i = 2; i <= n; i ++) {
        cin >> x >> h[i];
        g[x].push_back(i);
        //cout << x << " - " << i <<  "\n";
        cnt_r[h[i]] ++;
    }

    int u, v;
    for (int i = 1; i <= q; i ++) {
        cin >> u >> v;
        if (cnt_r[v] > m) {
            query_down[u].push_back(v);
        } else {
            query_up[v].push_back(u);
        }
        query[i] = {u, v};
    }

    predfs(1);
    dfs(1);
    memset(cur_cnt, 0, sizeof cur_cnt);
    dfs2(1);

    for (int i = 1; i <= q; i ++) {
        cout << ans[query[i].first][query[i].second] << "\n";
    }

    return 0;
}

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