제출 #731694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731694		Desh03	Regions (IOI09_regions)	C++17	19 / 100	8089 ms	25000 KiB

regions

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

vector<int> r[25000], g[200000], euler;
int in[200000], out[200000];
short int c[200000];
int t;

void dfs(int u) {
    in[u] = t++;
    euler.push_back(c[u]);
    for (int v : g[u])
        dfs(v);
    out[u] = t - 1;
}

int main() {
    int n, rr, qq;
    cin >> n >> rr >> qq;
    int x, h;
    cin >> h;
    h--;
    r[h].push_back(0);
    c[0] = h;
    for (int i = 1; i < n; i++) {
        cin >> x >> h;
        x--, h--;
        r[h].push_back(i);
        g[x].push_back(i);
        c[i] = h;
    }
    dfs(0);
    while (qq--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        int ans = 0;
        for (int u : r[a]) {
           for (int i = in[u] + 1; i <= out[u]; i++) {
                ans += euler[i] == b;
           }
        }
        cout << ans << '\n';
    }
}

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