oj.uz

Submission #731696

# Submission time Handle Problem Language Result Execution time Memory
731696 2023-04-27T19:52:11 Z Desh03 Regions (IOI09_regions) C++17
29 / 100
 8000 ms 26336 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6864 KB Output is correct
2 Correct 3 ms 6864 KB Output is correct
3 Correct 5 ms 6864 KB Output is correct
4 Correct 8 ms 6864 KB Output is correct
5 Correct 11 ms 7024 KB Output is correct
6 Correct 26 ms 7120 KB Output is correct
7 Correct 29 ms 7240 KB Output is correct
8 Correct 34 ms 7120 KB Output is correct
9 Correct 197 ms 7624 KB Output is correct
10 Correct 93 ms 7724 KB Output is correct
11 Correct 225 ms 8040 KB Output is correct
12 Correct 772 ms 8800 KB Output is correct
13 Correct 169 ms 8464 KB Output is correct
14 Correct 407 ms 8908 KB Output is correct
15 Execution timed out 8026 ms 11284 KB Time limit exceeded

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8058 ms 11516 KB Time limit exceeded
2 Execution timed out 8038 ms 11172 KB Time limit exceeded
3 Execution timed out 8074 ms 13376 KB Time limit exceeded
4 Correct 1322 ms 9772 KB Output is correct
5 Execution timed out 8068 ms 11784 KB Time limit exceeded
6 Correct 4119 ms 11544 KB Output is correct
7 Correct 2272 ms 12080 KB Output is correct
8 Execution timed out 8060 ms 15792 KB Time limit exceeded
9 Execution timed out 8025 ms 16344 KB Time limit exceeded
10 Execution timed out 8045 ms 20284 KB Time limit exceeded
11 Execution timed out 8089 ms 17432 KB Time limit exceeded
12 Execution timed out 8058 ms 17060 KB Time limit exceeded
13 Execution timed out 8093 ms 17224 KB Time limit exceeded
14 Execution timed out 8021 ms 16924 KB Time limit exceeded
15 Execution timed out 8083 ms 21080 KB Time limit exceeded
16 Execution timed out 8098 ms 26336 KB Time limit exceeded
17 Execution timed out 8048 ms 25148 KB Time limit exceeded