oj.uz

Submission #431047

# Submission time Handle Problem Language Result Execution time Memory
431047 2021-06-17T09:05:21 Z tengiz05 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 100420 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5, R = 550, 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 4 ms 6216 KB Output is correct
3 Correct 5 ms 6156 KB Output is correct
4 Correct 9 ms 6216 KB Output is correct
5 Correct 12 ms 6564 KB Output is correct
6 Correct 29 ms 8628 KB Output is correct
7 Correct 36 ms 6936 KB Output is correct
8 Correct 45 ms 7300 KB Output is correct
9 Correct 70 ms 18560 KB Output is correct
10 Correct 111 ms 8008 KB Output is correct
11 Correct 175 ms 9020 KB Output is correct
12 Correct 227 ms 18284 KB Output is correct
13 Correct 171 ms 8032 KB Output is correct
14 Correct 246 ms 8816 KB Output is correct
15 Correct 341 ms 100420 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 44524 KB Output is correct
2 Correct 1045 ms 14592 KB Output is correct
3 Correct 1517 ms 91320 KB Output is correct
4 Correct 304 ms 7936 KB Output is correct
5 Correct 316 ms 9876 KB Output is correct
6 Correct 1609 ms 9216 KB Output is correct
7 Correct 1957 ms 10292 KB Output is correct
8 Correct 1447 ms 16208 KB Output is correct
9 Correct 2802 ms 15920 KB Output is correct
10 Correct 5265 ms 21940 KB Output is correct
11 Correct 5481 ms 15544 KB Output is correct
12 Correct 7707 ms 16908 KB Output is correct
13 Execution timed out 8042 ms 17324 KB Time limit exceeded
14 Execution timed out 8041 ms 16876 KB Time limit exceeded
15 Execution timed out 8058 ms 22344 KB Time limit exceeded
16 Execution timed out 8077 ms 29456 KB Time limit exceeded
17 Execution timed out 8034 ms 27904 KB Time limit exceeded