oj.uz

Submission #738490

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

static constexpr int SQ = 350;

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 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 24 ms 336 KB Output is correct
7 Correct 31 ms 336 KB Output is correct
8 Correct 49 ms 484 KB Output is correct
9 Correct 60 ms 852 KB Output is correct
10 Correct 88 ms 1232 KB Output is correct
11 Correct 176 ms 1592 KB Output is correct
12 Correct 200 ms 2240 KB Output is correct
13 Correct 214 ms 2128 KB Output is correct
14 Correct 394 ms 2896 KB Output is correct
15 Correct 704 ms 5032 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1748 ms 7432 KB Output is correct
2 Correct 1710 ms 6524 KB Output is correct
3 Correct 4203 ms 9632 KB Output is correct
4 Correct 382 ms 3196 KB Output is correct
5 Correct 563 ms 4712 KB Output is correct
6 Correct 801 ms 12224 KB Output is correct
7 Correct 1493 ms 12880 KB Output is correct
8 Correct 1469 ms 28808 KB Output is correct
9 Correct 4677 ms 15224 KB Output is correct
10 Correct 4130 ms 61272 KB Output is correct
11 Correct 6463 ms 17796 KB Output is correct
12 Correct 1957 ms 19424 KB Output is correct
13 Correct 2798 ms 19524 KB Output is correct
14 Correct 3226 ms 26428 KB Output is correct
15 Correct 6011 ms 24680 KB Output is correct
16 Correct 6135 ms 29516 KB Output is correct
17 Correct 5364 ms 34024 KB Output is correct