제출 #955149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955149		uped	Regions (IOI09_regions)	C++14	100 / 100	3534 ms	60956 KiB

regions

#include <bits/stdc++.h>

#define DEBUG(x) cout << #x << ": " << x << '\n';

using namespace std;
using ll = long long;

const int N = 2e5;
const int R = 25001;

vector<int> adj[N];
int region[N];
int timer = 0;
int tin[N];
int tout[N];
vector<int> region_tin[R];
vector<int> region_nodes[R];
int region_size[R];

void tour(int n, int p = -1) {
    tin[n] = timer++;
    region_tin[region[n]].push_back(tin[n]);
    for (int x : adj[n]) {
        if (x == p) continue;
        tour(x, n);
    }
    tout[n] = timer++;
}

map<pair<int, int>, int> precalc_ans;

void precalc(int r, int n, int p = -1, int cnt = 0) {
    if (region[n] != r) precalc_ans[{r, region[n]}] += cnt;
    for (int x : adj[n]) {
        if (x == p) continue;
        precalc(r, x, n, cnt + (region[n] == r));
    }
    
}

int main() {
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[0];
    region_nodes[region[0]].push_back(0);
    region_size[region[0]]++;
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p >> region[i];
        region_size[region[i]]++;
        region_nodes[region[i]].push_back(i);
        adj[p - 1].push_back(i);
    }
    tour(0);
    for (int i = 1; i <= r; ++i) {
        if (region_size[i] > 500) precalc(i, 0);
    }

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        int ans = 0;
        if (region_size[a] <= 500) {
            for (int node : region_nodes[a]) {
                ans += upper_bound(region_tin[b].begin(), region_tin[b].end(), tout[node]) - lower_bound(region_tin[b].begin(), region_tin[b].end(), tin[node]);
            }
        } else {
            ans = precalc_ans[make_pair(a, b)];
        }
       
        cout << ans << endl;
    }
}

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