Submission #1150598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150598		polarity	Regions (IOI09_regions)	C++20	40 / 100	1877 ms	196608 KiB

regions

/**
 * Solution by 1egend (polarity.sh)
 * Date: 2025-02-15
 * Contest: IOI 2009
 * Problem: regions
**/

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

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

/** 
 * ALGORITHM: Euler Tour
 * PURPOSE: Flattens a tree so that each range contains any subtree range
 * CONSTRAINT: Graph must be a tree
 * TIME: O(V)
*/
vector<pii> eulerTour(int n, vector<vector<int>> &adj){
    vector<pii> ans(n);
    int i = -1;
    function<void(int, int)> tour;
    tour = [&](int node, int parent){
        ans[node].first = ++i;
        for (int x : adj[node]){
            if (x != parent){
                tour(x, node);
            }
        }
        ans[node].second = i;
    };

    // root at 0
    tour(0, 0);

    return ans;
}

void solve(){
    int n, r, q; cin >> n >> r >> q;
    vector<vi> adj(n);
    vi region(n);
    rep(i, 0, n){
        if (i == 0){
            cin >> region[0];
            region[0]--;
            continue;
        }

        int s; cin >> s;
        --s;
        adj[i].pb(s);
        adj[s].pb(i);

        cin >> region[i];
        region[i]--;
    }

    vector<pii> tree = eulerTour(n, adj);

    vi rend(n);
    vi arr(n);
    rep(i, 0, n){
        arr[tree[i].first] = region[i];
        rend[tree[i].first] = tree[i].second;
    }

    vi curr(r, 0);
    vector<vi> ans(r, vi(r, 0));

    using T = pii;
    priority_queue<T, vector<T>, greater<T>> pq;

    rep(i, 0, n){
        int a = arr[i];
        pq.push(pii{rend[i], a});
        curr[a]++;

        while(pq.top().first < i){
            curr[pq.top().second]--;
            pq.pop();
        }

        rep(j, 0, r){
            ans[j][a] += curr[j];
        }
    }


    rep(i, 0, q){
        int r1, r2; cin >> r1 >> r2;
        --r1; --r2;
        cout << ans[r1][r2] << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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