Submission #1261003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261003		spampots	Regions (IOI09_regions)	C++17	0 / 100	23 ms	10748 KiB

regions

#include <bits/stdc++.h>
using namespace std;

#define int long long

static inline int cnt_in_range(const vector<int>& v, int L, int R) {
    // count of x in v with L <= x <= R
    auto it1 = lower_bound(v.begin(), v.end(), (int)L);
    auto it2 = upper_bound(v.begin(), v.end(), (int)R);
    return (int)(it2 - it1);
}

void solve()
{
    int N, R, Q;
    if (!(cin >> N >> R >> Q)) return;

    vector<int> region(N + 1);
    vector<vector<int>> children(N + 1);

    // Employee 1: only region
    cin >> region[1];
    for (int k = 2; k <= N; ++k) {
        int s, h; cin >> s >> h;
        region[k] = h;
        children[s].push_back(k);
    }

    // Euler tour (iterative to avoid recursion limits)
    vector<int> tin(N + 1), tout(N + 1), euler(N + 1), idx(N + 1, 0);
    vector<int> st; st.reserve(N);
    vector<char> entered(N + 1, 0);
    int timer = 0;
    st.push_back(1);
    while (!st.empty()) {
        int u = st.back();
        if (!entered[u]) {
            entered[u] = 1;
            tin[u] = ++timer;
            euler[timer] = u;
        }
        if (idx[u] < (int)children[u].size()) {
            int v = children[u][idx[u]++];
            st.push_back(v);
        } else {
            tout[u] = timer;
            st.pop_back();
        }
    }
    // map tin -> tout for quick subtree interval from tin alone
    vector<int> toutAtTin(N + 1);
    for (int u = 1; u <= N; ++u) {
        toutAtTin[tin[u]] = tout[u];
    }

    // positions per region in Euler order
    vector<vector<int>> pos(R + 1);
    for (int i = 1; i <= N; ++i) {
        int u = euler[i];
        pos[region[u]].push_back(i); // i == tin[u], already sorted by construction
    }

    // heavy regions: size >= B
    int B = max<int>(1, (int)floor(sqrt((long double)N)));
    vector<int> heavyIndex(R + 1, -1);
    vector<int> heavyList;
    heavyList.reserve(R);
    for (int c = 1; c <= R; ++c) {
        if ((int)pos[c].size() >= B) {
            heavyIndex[c] = (int)heavyList.size();
            heavyList.push_back(c);
        }
    }

    // Precompute answers for heavy r1: heavyAns[h][r2] = answer for (r1=heavyList[h], r2)
    vector<vector<int>> heavyAns(heavyList.size(), vector<int>(R + 1, 0));
    vector<int> diff(N + 3, 0), f(N + 3, 0);

    for (int hi = 0; hi < (int)heavyList.size(); ++hi) {
        int a = heavyList[hi];

        // diff over Euler intervals of nodes in region a
        // mark all [tin[u], tout[u]] for u in a
        fill(diff.begin(), diff.end(), 0);
        for (int t : pos[a]) {
            int L = t;
            int Rr = toutAtTin[t];
            ++diff[L];
            --diff[Rr + 1];
        }

        // prefix to get f[i] = number of 'a' ancestors including self at node euler[i]
        int cur = 0;
        for (int i = 1; i <= N; ++i) {
            cur += diff[i];
            f[i] = cur;
        }

        // accumulate to answers per region r2, subtract self if same region (proper ancestor)
        for (int i = 1; i <= N; ++i) {
            int v = euler[i];
            int r2 = region[v];
            int add = f[i] - (r2 == a ? 1 : 0);
            if (add) heavyAns[hi][r2] += add;
        }
    }

    // Process queries online
    for (int qi = 0; qi < Q; ++qi) {
        int r1, r2; cin >> r1 >> r2;

        int ans = 0;
        int hi = heavyIndex[r1];
        if (hi != -1) {
            // heavy r1: O(1)
            ans = heavyAns[hi][r2];
        } else {
            // light r1: sum over nodes u in r1 of count(r2 in subtree(u))
            const auto &A = pos[r1];
            const auto &Bv = pos[r2];
            for (int t : A) {
                int L = t, Rr = toutAtTin[t];
                ans += cnt_in_range(Bv, L, Rr);
            }
            if (r1 == r2) ans -= (int)A.size(); // remove (u,u) self-pairs
        }

        cout << ans << '\n';
        cout.flush(); // important for interactive behavior
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    if (!(cin >> t)) return 0; // set to 1 when the judge doesn't provide t
    while (t--)
        solve();
}

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