Submission #1269476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269476		newsboy	Regions (IOI09_regions)	C++20	4 / 100	3327 ms	41000 KiB

regions

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <utility>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

struct HLD {
    i64 n;
    vector<i64> siz, top, dep, parent, in, out, seq;
    vector<vector<i64>> adj;
    i64 cur;
    HLD() {}
    HLD(i64 n) {
        init(n);
    }
    void init(i64 n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        adj.assign(n, {});
        cur = 0;
    }
    void addEdge(i64 u, i64 v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(i64 root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(i64 u) {
        if (parent[u] != -1) {
            adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        siz[u] = 1;
        for (auto& v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(i64 u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n, m, q;
    cin >> n >> m >> q;
    constexpr i64 B = 450;
    HLD t(n);
    vector<i64> a(n), c(m + 1);
    for (i64 i = 0; i < n; i++) {
        if (i == 0) {
            cin >> a[i];
        }
        else {
            i64 p;
            cin >> p >> a[i];
            p--;
            t.addEdge(p, i);
        }
        c[a[i]]++;
    }
    t.work();
    vector<vector<i64>> b(m + 1);
    for (i64 i = 0; i < n; i++) {
        b[a[i]].push_back(t.in[i]);
    }
    for (i64 i = 1; i <= m; i++) {
        sort(b[i].begin(), b[i].end());
    }
    map<i64, vector<i64>> f;
    auto dfs = [&](auto& self, i64 u, i64 h, i64 cnt) -> void {
        f[h][a[u]] += cnt;
        if (a[u] == h) {
            cnt++;
        }
        for (auto v : t.adj[u]) {
            self(self, v, h, cnt);
        }
        };
    for (i64 i = 1; i <= m; i++) {
        if (c[i] >= B) {
            f[i].resize(m + 1);
            dfs(dfs, 0, i, 0);
        }
    }
    while (q--) {
        i64 x, y;
        cin >> x >> y;
        i64 ans = 0;
        if (c[x] < B) {
            for (auto u : b[x]) {
                ans += lower_bound(b[y].begin(), b[y].end(), t.out[u]) - upper_bound(b[y].begin(), b[y].end(), t.in[u]);
            }
        }
        else {
            ans = f[x][y];
        }
        cout << ans << endl;
    }
}

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