제출 #731694

#제출 시각아이디문제언어결과실행 시간메모리
731694Desh03Regions (IOI09_regions)C++17
19 / 100
8089 ms25000 KiB
#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';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...