oj.uz

Submission #430980

# Submission time Handle Problem Language Result Execution time Memory
430980 2021-06-17T08:41:04 Z tengiz05 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 97300 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5, R = 500;
int ans[R][R];
std::vector<int> e[N], c[R * R];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, q;
    std::cin >> n >> m >> q;
    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]; };
    if (m <= 500) {
        std::vector<int> last;
        std::function<void(int)> dfs2 = [&](int u) {
            std::vector<int> t(R);
            for (auto v : e[u]) {
                dfs2(v);
                for (int i = 0; i < R; i++) {
                    t[i] += last[i];
                }
            }
            t[a[u]]++;
            for (int i = 0; i < R; i++) {
                ans[a[u]][i] += t[i];
            }
            last = t;
        };
        dfs2(0);
        while (q--) {
            int r1, r2;
            std::cin >> r1 >> r2;
            r1--;
            r2--;
            std::cout << ans[r1][r2] << std::endl;
        }
        return 0;
    }
    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 7 ms 10824 KB Output is correct
2 Correct 9 ms 10824 KB Output is correct
3 Correct 10 ms 10952 KB Output is correct
4 Correct 12 ms 10952 KB Output is correct
5 Correct 12 ms 11208 KB Output is correct
6 Correct 34 ms 13080 KB Output is correct
7 Correct 47 ms 11396 KB Output is correct
8 Correct 30 ms 11876 KB Output is correct
9 Correct 70 ms 22220 KB Output is correct
10 Correct 100 ms 12564 KB Output is correct
11 Correct 159 ms 13420 KB Output is correct
12 Correct 246 ms 21988 KB Output is correct
13 Correct 216 ms 12476 KB Output is correct
14 Correct 226 ms 13196 KB Output is correct
15 Correct 371 ms 97300 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1096 ms 45956 KB Output is correct
2 Correct 1109 ms 18412 KB Output is correct
3 Correct 1457 ms 88996 KB Output is correct
4 Correct 307 ms 12340 KB Output is correct
5 Correct 475 ms 14324 KB Output is correct
6 Execution timed out 8096 ms 13500 KB Time limit exceeded
7 Correct 7192 ms 14404 KB Output is correct
8 Correct 4119 ms 20196 KB Output is correct
9 Correct 7430 ms 19416 KB Output is correct
10 Execution timed out 8077 ms 25136 KB Time limit exceeded
11 Execution timed out 8071 ms 18748 KB Time limit exceeded
12 Execution timed out 8015 ms 20324 KB Time limit exceeded
13 Execution timed out 8047 ms 20796 KB Time limit exceeded
14 Execution timed out 8057 ms 20336 KB Time limit exceeded
15 Execution timed out 8048 ms 25408 KB Time limit exceeded
16 Execution timed out 8051 ms 32760 KB Time limit exceeded
17 Execution timed out 8042 ms 31196 KB Time limit exceeded