Submission #1131124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131124		minhnguyent546	Regions (IOI09_regions)	C++20	70 / 100	4807 ms	18508 KiB

regions

/**            
 * author      minhnguyent546
 * created_at  Wed, 2025-01-01 16:52:58
 * problem     https://oj.uz/problem/view/IOI09_regions
 **/           
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif

int n, r, q;
const int N = (int) 2e5 + 3;
const int R = (int) 25e3 + 3;
vector<int> g[N];
int house[N], par[N];
vector<int> vers[R];
int tin[N], tout[N];
int timer = 0;

void dfs(int u) {
    tin[u] = timer++;
    for (int v : g[u]) {
        dfs(v);
    }
    tout[u] = timer - 1;
}

template<typename T>
struct Fenwick {
    int n;
    vector<T> tree;
    Fenwick() {}
    Fenwick(int _n): n(_n), tree(n) {}
    void add(int i, T val) {
        while (i < n) {
            tree[i] += val;
            i |= (i + 1);
        }
    }
    T pref(int i) {
        T res{};
        while (i >= 0) {
            res += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return res;
    }
    T query(int l, int r) { return pref(r) - pref(l - 1); }
};

void read_input() {
    cin >> n >> r >> q;
    cin >> house[0];
    --house[0];
    for (int i = 1; i < n; ++i) {
        int x, h;
        cin >> x >> h;
        --x; --h;
        par[i] = x;
        g[x].emplace_back(i);
        house[i] = h;
    }

    for (int i = 0; i < n; ++i) {
        vers[house[i]].emplace_back(i);
    }
}

namespace sub1 {
bool check() {
    return r <= 500;
}

void solve() {
    dfs(0);
    vector<vector<long long>> cnt(r, vector<long long>(r));
    Fenwick<int> tree(n);
    for (int r1 = 0; r1 < r; ++r1) {
        for (int r2 = 0; r2 < r; ++r2) {
            if (r2 == r1) continue;
            for (int ver : vers[r2]) {
                tree.add(tin[ver], 1);
            }
            for (int ver : vers[r1]) {
                cnt[r1][r2] += tree.query(tin[ver] + 1, tout[ver]);
            }

            // reset
            for (int ver : vers[r2]) {
                tree.add(tin[ver], -1);
            }
        }
    }
    for (int w = 0; w < q; ++w) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1; --r2;
        cout << cnt[r1][r2] << endl;
    }
}
} // namespace sub1

namespace sub2 {
bool check() {
    for (int i = 0; i < r; ++i) {
        if ((int) vers[i].size() > 500) return false;
    }
    return true;
}

void solve() {
    dfs(0);
    Fenwick<int> tree(n);
    for (int w = 0; w < q; ++w) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1; --r2;
        assert(r1 != r2);
        for (int ver : vers[r2]) {
            tree.add(tin[ver], 1);
        }
        long long ans = 0;
        for (int ver : vers[r1]) {
            ans += tree.query(tin[ver] + 1, tout[ver]);
        }

        // reset
        for (int ver : vers[r2]) {
            tree.add(tin[ver], -1);
        }

        cout << ans << endl;
    }
}
} // namespace sub2 

namespace sub3 {
bool check() {
    return false;
}

void solve() {

}
} // namespace sub3
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    read_input();

    #ifdef LOCAL
        sub1::solve();
        return 0;
    #endif

    if (sub1::check()) {
        sub1::solve();
        return 0;
    }
    if (sub2::check()) {
        sub2::solve();
        return 0;
    }

    if (sub3::check()) {
        sub3::solve();
        return 0;
    }
    assert(false);
    
    return 0;
}

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