oj.uz

Submission #431040

# Submission time Handle Problem Language Result Execution time Memory
431040 2021-06-17T09:03:57 Z tengiz05 Regions (IOI09_regions) C++17
64 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5, R = 700;
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 <= 700) {
        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++) {
        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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27944 KB Output is correct
2 Correct 18 ms 27972 KB Output is correct
3 Correct 26 ms 28048 KB Output is correct
4 Correct 21 ms 28132 KB Output is correct
5 Correct 26 ms 28440 KB Output is correct
6 Correct 41 ms 31072 KB Output is correct
7 Correct 53 ms 28768 KB Output is correct
8 Correct 55 ms 29416 KB Output is correct
9 Correct 89 ms 43456 KB Output is correct
10 Correct 129 ms 30212 KB Output is correct
11 Correct 159 ms 31336 KB Output is correct
12 Correct 226 ms 43072 KB Output is correct
13 Correct 236 ms 30100 KB Output is correct
14 Correct 239 ms 30972 KB Output is correct
15 Runtime error 91 ms 131076 KB Execution killed with signal 9

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 75260 KB Output is correct
2 Correct 1233 ms 37724 KB Output is correct
3 Runtime error 133 ms 131076 KB Execution killed with signal 9
4 Correct 303 ms 29628 KB Output is correct
5 Correct 418 ms 31712 KB Output is correct
6 Correct 1562 ms 31056 KB Output is correct
7 Correct 2115 ms 32140 KB Output is correct
8 Correct 1714 ms 38056 KB Output is correct
9 Correct 3147 ms 37764 KB Output is correct
10 Correct 6087 ms 43784 KB Output is correct
11 Correct 5863 ms 37388 KB Output is correct
12 Execution timed out 8073 ms 38752 KB Time limit exceeded
13 Execution timed out 8036 ms 39196 KB Time limit exceeded
14 Execution timed out 8055 ms 38720 KB Time limit exceeded
15 Execution timed out 8009 ms 44188 KB Time limit exceeded
16 Execution timed out 8052 ms 51356 KB Time limit exceeded
17 Execution timed out 8058 ms 49760 KB Time limit exceeded