제출 #1162397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162397		nh0902	Regions (IOI09_regions)	C++20	100 / 100	3750 ms	118168 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];

vector<int> ans;

vector<int> ans_pos[R], ans_pos_rv[R];

vector<pair<int, 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);
    }

    /*
    cout << u << "\n";
    for (int i = 1; i <= r; i ++) {
        cout << i << " : " << cur_cnt[i] << "\n";
    }
    cout << "\n";
    */

    for (pair<int, int> x : query_down[h[u]]) {
        ans[x.second] += cur_cnt[x.first];
    }

    cur_cnt[h[u]] ++;
}

void dfs2(int u) {
    for (pair<int, int> x : query_up[h[u]]) {
        ans[x.second] += cur_cnt[x.first];
    }

    cur_cnt[h[u]] ++;

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

    cur_cnt[h[u]] --;
}

vector<int> pos_r[R];

int be[N], en[N];

int cur;

void euler(int u) {
    cur ++;
    be[u] = cur;
    for (int v : g[u]) euler(v);
    en[u] = cur;
}

int bit[N];

int get(int p) {
    int idx = p, ans = 0;
    while (idx > 0) {
        ans += bit[idx];
        idx -= (idx & (-idx));
    }
    return ans;
}

void upd(int u, int v) {
    int idx = u;
    while (idx <= n) {
        bit[idx] += v;
        idx += (idx & (-idx));
    }
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(nullptr);

    // 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);

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

    cin >> h[1];
    cnt_r[h[1]] ++;
    pos_r[h[1]].push_back(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]] ++;
        pos_r[h[i]].push_back(i);
    }

    int query_id = - 1;
    for (int i = 1; i <= r; i ++) {
        if (cnt_r[i] < m) continue;
        for (int j = 1; j <= r; j ++) {
            query_id ++;
            ans.push_back(0);
            ans_pos[i].push_back(query_id);
            query_up[j].push_back({i, query_id});
            query_id ++;
            ans.push_back(0);
            ans_pos_rv[i].push_back(query_id);
            query_down[j].push_back({i, query_id});
        }
    }

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

    euler(1);

    int u, v;

    while (q --) {
        cin >> u >> v;
        if (cnt_r[u] >= m) {
            cout << ans[ans_pos[u][v - 1]] << endl;
        } else if (cnt_r[v] >= m) {
            cout << ans[ans_pos_rv[v][u - 1]] << endl;
        } else {
            for (int x : pos_r[v]) {
                upd(be[x], 1);
            }
            int ret = 0;
            for (int x : pos_r[u]) {
                ret += get(en[x]) - get(be[x] - 1);
            }

            if (u == v) {
                ret -= pos_r[u].size();
            }

            cout << ret << endl;

            for (int x : pos_r[v]) {
                upd(be[x], - 1);
            }


        }
    }

    return 0;
}

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