oj.uz

Submission #731698

# Submission time Handle Problem Language Result Execution time Memory
731698 2023-04-27T20:01:12 Z Desh03 Regions (IOI09_regions) C++17
13 / 100
 3519 ms 131072 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 11 ms 816 KB Output is correct
6 Correct 35 ms 6236 KB Output is correct
7 Correct 40 ms 2444 KB Output is correct
8 Correct 54 ms 4616 KB Output is correct
9 Correct 464 ms 65768 KB Output is correct
10 Correct 200 ms 17196 KB Output is correct
11 Correct 539 ms 48908 KB Output is correct
12 Runtime error 734 ms 131072 KB Execution killed with signal 9
13 Correct 467 ms 28236 KB Output is correct
14 Correct 1201 ms 89828 KB Output is correct
15 Runtime error 3519 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 2351 ms 131072 KB Execution killed with signal 9
2 Runtime error 1803 ms 131072 KB Execution killed with signal 9
3 Runtime error 2925 ms 131072 KB Execution killed with signal 9
4 Runtime error 693 ms 131072 KB Execution killed with signal 9
5 Runtime error 878 ms 131072 KB Execution killed with signal 9
6 Runtime error 709 ms 131072 KB Execution killed with signal 9
7 Runtime error 668 ms 131072 KB Execution killed with signal 9
8 Runtime error 894 ms 131072 KB Execution killed with signal 9
9 Runtime error 851 ms 131072 KB Execution killed with signal 9
10 Runtime error 919 ms 131072 KB Execution killed with signal 9
11 Runtime error 878 ms 131072 KB Execution killed with signal 9
12 Runtime error 999 ms 131072 KB Execution killed with signal 9
13 Runtime error 976 ms 131072 KB Execution killed with signal 9
14 Runtime error 984 ms 131072 KB Execution killed with signal 9
15 Runtime error 789 ms 131072 KB Execution killed with signal 9
16 Runtime error 823 ms 131072 KB Execution killed with signal 9
17 Runtime error 884 ms 131072 KB Execution killed with signal 9