Submission #731696

#	Time	Username	Problem	Language	Result	Execution time	Memory
731696		Desh03	Regions (IOI09_regions)	C++17	29 / 100	8098 ms	26336 KiB

regions

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

unordered_map<short int, int> mp[25000];
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--;
        if (mp[a].find(b) != mp[a].end()) {
            cout << mp[a][b] << '\n';
            continue;
        }
        int ans = 0;
        for (int u : r[a]) {
           for (int i = in[u] + 1; i <= out[u]; i++) {
                ans += euler[i] == b;
           }
        }
        mp[a][b] = ans;
        cout << ans << '\n';
    }
}

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