oj.uz

Submission #431026

# Submission time Handle Problem Language Result Execution time Memory
431026 2021-06-17T08:59:40 Z tengiz05 Regions (IOI09_regions) C++17
80 / 100
 8000 ms 103436 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++) {
        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 13 ms 16672 KB Output is correct
2 Correct 11 ms 16780 KB Output is correct
3 Correct 13 ms 16828 KB Output is correct
4 Correct 16 ms 16876 KB Output is correct
5 Correct 22 ms 17008 KB Output is correct
6 Correct 25 ms 18952 KB Output is correct
7 Correct 53 ms 17352 KB Output is correct
8 Correct 53 ms 17716 KB Output is correct
9 Correct 84 ms 28180 KB Output is correct
10 Correct 115 ms 18472 KB Output is correct
11 Correct 159 ms 19372 KB Output is correct
12 Correct 203 ms 28048 KB Output is correct
13 Correct 176 ms 18540 KB Output is correct
14 Correct 255 ms 19352 KB Output is correct
15 Correct 326 ms 103436 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 52264 KB Output is correct
2 Correct 1028 ms 24736 KB Output is correct
3 Correct 1676 ms 95252 KB Output is correct
4 Correct 319 ms 18320 KB Output is correct
5 Correct 419 ms 20432 KB Output is correct
6 Correct 1433 ms 19776 KB Output is correct
7 Correct 1939 ms 20852 KB Output is correct
8 Correct 1657 ms 26768 KB Output is correct
9 Correct 3657 ms 26480 KB Output is correct
10 Correct 6116 ms 32504 KB Output is correct
11 Correct 5638 ms 26112 KB Output is correct
12 Correct 7879 ms 27472 KB Output is correct
13 Correct 7771 ms 27920 KB Output is correct
14 Execution timed out 8042 ms 27476 KB Time limit exceeded
15 Execution timed out 8067 ms 32844 KB Time limit exceeded
16 Execution timed out 8083 ms 39972 KB Time limit exceeded
17 Execution timed out 8095 ms 38440 KB Time limit exceeded