oj.uz

Submission #430956

# Submission time Handle Problem Language Result Execution time Memory
430956 2021-06-17T08:21:51 Z tengiz05 Regions (IOI09_regions) C++17
40 / 100
 8000 ms 27412 KB 
#include <bits/stdc++.h>
using i64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<int>> e(n), c(m);
    std::vector<int> a(n);
    std::cin >> a[0];
    for (int i = 1, p; i < n; i++) {
        std::cin >> p >> a[i];
        p--;
        e[p].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        c[--a[i]].push_back(i);
    }
    std::vector<int> in(n), out(n);
    int timeStamp = 0;
    std::function<void(int)> dfs = [&](int u) {
        in[u] = timeStamp++;
        for (auto v : e[u]) {
            dfs(v);
        }
        out[u] = timeStamp;
    };
    dfs(0);
    auto is = [&](int u, int v) { return in[u] < in[v] && out[u] >= out[v]; };
    while (q--) {
        int r1, r2;
        std::cin >> r1 >> r2;
        r1--;
        r2--;
        int ans = 0;
        for (auto u : c[r1]) {
            for (auto v : c[r2]) {
                if (is(u, v)) {
                    ans++;
                }
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 4 ms 200 KB Output is correct
4 Correct 7 ms 200 KB Output is correct
5 Correct 6 ms 328 KB Output is correct
6 Correct 14 ms 328 KB Output is correct
7 Correct 33 ms 328 KB Output is correct
8 Correct 33 ms 456 KB Output is correct
9 Correct 44 ms 904 KB Output is correct
10 Correct 97 ms 968 KB Output is correct
11 Correct 201 ms 1452 KB Output is correct
12 Correct 190 ms 2084 KB Output is correct
13 Correct 436 ms 1748 KB Output is correct
14 Correct 1128 ms 2432 KB Output is correct
15 Correct 1281 ms 5780 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8057 ms 6580 KB Time limit exceeded
2 Execution timed out 8026 ms 5308 KB Time limit exceeded
3 Execution timed out 8032 ms 8968 KB Time limit exceeded
4 Correct 328 ms 2576 KB Output is correct
5 Correct 446 ms 4732 KB Output is correct
6 Execution timed out 8007 ms 4324 KB Time limit exceeded
7 Correct 7475 ms 5712 KB Output is correct
8 Correct 4429 ms 12240 KB Output is correct
9 Correct 6945 ms 12712 KB Output is correct
10 Execution timed out 8038 ms 19200 KB Time limit exceeded
11 Execution timed out 8052 ms 13372 KB Time limit exceeded
12 Execution timed out 8055 ms 14668 KB Time limit exceeded
13 Execution timed out 8048 ms 15124 KB Time limit exceeded
14 Execution timed out 8063 ms 14936 KB Time limit exceeded
15 Execution timed out 8048 ms 20240 KB Time limit exceeded
16 Execution timed out 8019 ms 27412 KB Time limit exceeded
17 Execution timed out 8071 ms 25776 KB Time limit exceeded