oj.uz

Submission #431021

# Submission time Handle Problem Language Result Execution time Memory
431021 2021-06-17T08:58:50 Z tengiz05 Regions (IOI09_regions) C++17
55 / 100
 5641 ms 80988 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], actual[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);
    }
    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);
    for (int i = 0; i < n; i++) {
        c[--a[i]].push_back(in[i]);
        actual[a[i]].push_back(i);
    }
    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;
    // }
    for (int i = 0; i < R * R; i++) {
        if (c[i].size() > 500) assert(false);
        std::sort(c[i].begin(), c[i].end());
    }
    while (q--) {
        int r1, r2;
        std::cin >> r1 >> r2;
        r1--;
        r2--;
        int ans = 0;
        for (auto u : actual[r1]) {
            ans += upper_bound(c[r2].begin(), c[r2].end(), out[u] - 1) - upper_bound(c[r2].begin(), c[r2].end(), in[u] - 1);
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:32:10: warning: variable 'is' set but not used [-Wunused-but-set-variable]
   32 |     auto is = [&](int u, int v) { return in[u] < in[v] && out[u] >= out[v]; };
      |          ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16684 KB Output is correct
2 Correct 12 ms 16712 KB Output is correct
3 Correct 14 ms 16624 KB Output is correct
4 Correct 17 ms 16744 KB Output is correct
5 Correct 18 ms 16712 KB Output is correct
6 Correct 28 ms 16840 KB Output is correct
7 Correct 35 ms 16840 KB Output is correct
8 Correct 37 ms 16864 KB Output is correct
9 Correct 66 ms 17388 KB Output is correct
10 Correct 98 ms 17224 KB Output is correct
11 Correct 151 ms 17528 KB Output is correct
12 Correct 185 ms 18004 KB Output is correct
13 Correct 221 ms 17740 KB Output is correct
14 Correct 357 ms 18320 KB Output is correct
15 Correct 312 ms 21540 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 43716 KB Execution killed with signal 6
2 Runtime error 57 ms 41024 KB Execution killed with signal 6
3 Runtime error 62 ms 47996 KB Execution killed with signal 6
4 Correct 299 ms 18392 KB Output is correct
5 Correct 425 ms 20444 KB Output is correct
6 Correct 1689 ms 19784 KB Output is correct
7 Correct 2253 ms 20860 KB Output is correct
8 Correct 1821 ms 26776 KB Output is correct
9 Correct 3191 ms 26484 KB Output is correct
10 Correct 5588 ms 32504 KB Output is correct
11 Correct 5641 ms 26104 KB Output is correct
12 Runtime error 143 ms 55448 KB Execution killed with signal 6
13 Runtime error 140 ms 56332 KB Execution killed with signal 6
14 Runtime error 128 ms 55616 KB Execution killed with signal 6
15 Runtime error 138 ms 66576 KB Execution killed with signal 6
16 Runtime error 129 ms 80988 KB Execution killed with signal 6
17 Runtime error 130 ms 77860 KB Execution killed with signal 6