oj.uz

Submission #738487

# Submission time Handle Problem Language Result Execution time Memory
738487 2023-05-08T20:38:04 Z lorenzoferrari Regions (IOI09_regions) C++17
95 / 100
 5846 ms 131072 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
using LL = long long;

static constexpr int SQ = 256;

struct Segtree {
    int n;
    vector<int> t;
    Segtree(int n) : n(n), t(2*n) {}
    void update(int p, int v) {
        for (t[p += n] += v; p > 1; p >>= 1) {
            t[p >> 1] = t[p] + t[p ^ 1];
        }
    }
    int query(int l, int r) {
        int ans = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans += t[l++];
            if (r & 1) ans += t[--r];
        }
        return ans;
    }
};

int main() {
    int n; cin >> n;
    int r; cin >> r;
    int q; cin >> q;
    vector<int> h(n), p(n), f(r);
    vector<vector<int>> adj(n);
    cin >> h[0]; ++f[--h[0]];
    for (int i = 1; i < n; ++i) {
        cin >> p[i] >> h[i];
        --p[i], --h[i];
        adj[p[i]].push_back(i);
        ++f[h[i]];
    }
    vector<int> ff;
    vector<int> fi(r, -1);
    for (int i = 0; i < r; ++i) {
        if (f[i] >= SQ) {
            fi[i] = ff.size();
            ff.push_back(i);
        }
    }
    int nn = ff.size();

    vector<int> in(n), out(n), ord;
    { // linearize the tree
        int t = 0;
        auto dfs = [&](auto&& self, int v) -> void {
            in[v] = t++;
            ord.push_back(v);
            for (int u : adj[v]) {
                self(self, u);
            }
            out[v] = t;
        };
        dfs(dfs, 0);
    }

    vector<vector<int>> vs(r);
    for (int v : ord) {
        vs[h[v]].push_back(v);
    }

    vector<vector<LL>> sub(r, vector<LL>(nn));
    vector<vector<LL>> anc(r, vector<LL>(nn));
    {
        auto dfs = [&](auto&& self, int v, int i, int acc = 0) -> int {
            int cnt = 0;
            for (int u : adj[v]) {
                cnt += self(self, u, i, acc + (h[v] == ff[i]));
            }
            sub[h[v]][i] += cnt;
            anc[h[v]][i] += acc;
            return cnt + (h[v] == ff[i]);
        };
        for (int i = 0; i < nn; ++i) {
            dfs(dfs, 0, i);
        }
    }

    Segtree st(n);
    for (int r1, r2; q--;) {
        cin >> r1 >> r2;
        --r1, --r2;
        if (f[r2] >= SQ) {
            cout << sub[r1][fi[r2]] << endl;
        } else if (f[r1] >= SQ) {
            cout << anc[r2][fi[r1]] << endl;
        } else {
            LL ans = 0;
            for (int v : vs[r2]) {
                st.update(in[v], 1);
            }
            for (int u : vs[r1]) {
                ans += st.query(in[u]+1, out[u]);
            }
            for (int v : vs[r2]) {
                st.update(in[v], -1);
            }
            cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 25 ms 336 KB Output is correct
7 Correct 33 ms 416 KB Output is correct
8 Correct 53 ms 464 KB Output is correct
9 Correct 67 ms 848 KB Output is correct
10 Correct 95 ms 1172 KB Output is correct
11 Correct 187 ms 1592 KB Output is correct
12 Correct 226 ms 2252 KB Output is correct
13 Correct 217 ms 2148 KB Output is correct
14 Correct 398 ms 2892 KB Output is correct
15 Correct 827 ms 5040 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 7464 KB Output is correct
2 Correct 1313 ms 6764 KB Output is correct
3 Correct 4315 ms 9640 KB Output is correct
4 Correct 467 ms 3200 KB Output is correct
5 Correct 687 ms 4724 KB Output is correct
6 Correct 842 ms 12224 KB Output is correct
7 Correct 1395 ms 15388 KB Output is correct
8 Correct 1537 ms 28808 KB Output is correct
9 Correct 3439 ms 39432 KB Output is correct
10 Correct 3737 ms 61276 KB Output is correct
11 Runtime error 180 ms 131072 KB Execution killed with signal 9
12 Correct 1959 ms 19424 KB Output is correct
13 Correct 2858 ms 19528 KB Output is correct
14 Correct 2997 ms 26436 KB Output is correct
15 Correct 5544 ms 24764 KB Output is correct
16 Correct 5846 ms 29512 KB Output is correct
17 Correct 4994 ms 34024 KB Output is correct