제출 #955136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955136		uped	Regions (IOI09_regions)	C++14	80 / 100	8087 ms	26712 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];

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++;
}

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

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        int ans = 0;
        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]);
        }
        cout << ans << endl;
    }
}

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