제출 #1241557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241557		turska	Regions (IOI09_regions)	C++20	100 / 100	2063 ms	54124 KiB

regions

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

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
// const ll M = 998244353; 
const ll M = 1e9 + 7;
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second

const ll INFL = 1e18;
const int INF = 1e9;
const int mxN = 2e5;
const int mxR = 25000;
const int Z = 2000;


vector<int> adj[mxN];
int freq[mxR], tin[mxN], tout[mxN], ord[mxR], color[mxN], rnk[mxR];
int pre[Z][Z];
int cur[Z];

int timer = -1;
int n, r, q;

vector<int> with_color[mxR];
vector<int> tins[mxR];
vector<array<int,2 >> edge_pref[mxR];
void dfs(int v) {
    tin[v] = ++timer;
    edge_pref[color[v]].push_back({tin[v], edge_pref[color[v]].back()[1]+1});
    tins[color[v]].push_back(tin[v]);

    if (rnk[color[v]]<Z) {
        for (int i=0; i<Z; i++) {
            pre[i][rnk[color[v]]] += cur[i];
        }
        cur[rnk[color[v]]]++;
    }
    for (auto u: adj[v]) dfs(u);
    if (rnk[color[v]]<Z) cur[rnk[color[v]]]--;
    tout[v] = ++timer;

    edge_pref[color[v]].push_back({tout[v], edge_pref[color[v]].back()[1]-1});
}


// for each in a calc count of b in subtree
int calc_1(int a, int b) {
    int res = 0;
    for (auto i: with_color[a]) {
        res += upper_bound(all(tins[b]), tout[i])-lower_bound(all(tins[b]), tin[i]);
    }
    return res;
}
// for each in b calc parents with a
int calc_2(int a, int b) {
    int res = 0;
    for (auto i: with_color[b]) {
        auto it = upper_bound(all(edge_pref[a]), array<int,2>{tin[i], 0});
        it--;
        res += (*it)[1];
    }
    return res;
}




void solve() {
    cin >> n >> r >> q;
    cin >> color[0];
    color[0]--;
    for (int i=1; i<n; i++) {
        int s;
        cin >> s >> color[i];
        color[i]--; s--;
        adj[s].push_back(i);
    }
    for (int i=0; i<n; i++) freq[color[i]]++;
    iota(ord, ord+r, 0);
    sort(ord, ord+r, [&](int l, int r) {
        return freq[l] > freq[r];
    });
    for (int i=0; i<r; i++) rnk[ord[i]] = i;
    for (int i=0; i<r; i++) edge_pref[i].push_back({-1, 0});
    for (int i=0; i<n; i++) with_color[color[i]].push_back(i);
    dfs(0);

    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        r1--; r2--;
        if (rnk[r1]>=Z) cout << calc_1(r1, r2) << endl;
        else if (rnk[r2]>=Z) cout << calc_2(r1, r2) << endl;
        else cout << pre[rnk[r1]][rnk[r2]] << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1;
    // cin >> tc;
    while (tc--) solve();
}

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