oj.uz

Submission #431072

# Submission time Handle Problem Language Result Execution time Memory
431072 2021-06-17T09:16:26 Z tengiz05 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 108604 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5, R = 600, RR = 25000;
int ans[R][R];
std::vector<int> e[N], c[RR], actual[RR];
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 <= R) {
        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 < RR; 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6088 KB Output is correct
2 Correct 5 ms 6216 KB Output is correct
3 Correct 7 ms 6216 KB Output is correct
4 Correct 7 ms 6216 KB Output is correct
5 Correct 13 ms 6588 KB Output is correct
6 Correct 24 ms 8776 KB Output is correct
7 Correct 35 ms 6856 KB Output is correct
8 Correct 39 ms 7368 KB Output is correct
9 Correct 75 ms 19572 KB Output is correct
10 Correct 122 ms 8120 KB Output is correct
11 Correct 167 ms 9164 KB Output is correct
12 Correct 216 ms 19332 KB Output is correct
13 Correct 229 ms 8112 KB Output is correct
14 Correct 259 ms 8916 KB Output is correct
15 Correct 371 ms 108604 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1118 ms 47620 KB Output is correct
2 Correct 1162 ms 15084 KB Output is correct
3 Correct 1634 ms 98564 KB Output is correct
4 Correct 270 ms 7880 KB Output is correct
5 Correct 383 ms 9880 KB Output is correct
6 Correct 1548 ms 9220 KB Output is correct
7 Correct 1910 ms 10304 KB Output is correct
8 Correct 1310 ms 16208 KB Output is correct
9 Correct 2760 ms 15928 KB Output is correct
10 Correct 4968 ms 21944 KB Output is correct
11 Correct 5040 ms 15552 KB Output is correct
12 Correct 7562 ms 16912 KB Output is correct
13 Execution timed out 8045 ms 17360 KB Time limit exceeded
14 Execution timed out 8015 ms 17000 KB Time limit exceeded
15 Execution timed out 8020 ms 22284 KB Time limit exceeded
16 Execution timed out 8013 ms 29504 KB Time limit exceeded
17 Execution timed out 8061 ms 27920 KB Time limit exceeded