Submission #731698

#	Time	Username	Problem	Language	Result	Execution time	Memory
731698		Desh03	Regions (IOI09_regions)	C++17	13 / 100	3519 ms	131072 KiB

regions

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

vector<unordered_map<short int, int>> mp;
vector<unordered_map<int, int>> mp2;
vector<vector<int>> r, g;
vector<int> euler, in, out, c;
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;
    mp2.resize(n), mp.resize(rr), g.resize(n), r.resize(rr), in.resize(n), out.resize(n), c.resize(n);
    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]) {
           if (mp2[u].size()) {
                ans += mp2[u][b];
                continue;
           }
           unordered_map<int, int> fr;
           for (int i = in[u] + 1; i <= out[u]; i++) {
                fr[euler[i]]++;
           }
           for (auto [x, y] : fr) mp2[u][x] = y;
           ans += fr[b];
        }
        mp[a][b] = ans;
        cout << ans << '\n';
    }
}

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