oj.uz

Submission #738932

# Submission time Handle Problem Language Result Execution time Memory
738932 2023-05-09T16:40:54 Z lorenzoferrari Regions (IOI09_regions) C++17
100 / 100
 6058 ms 65992 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
using LL = long long;

static constexpr int N = 200000;
static constexpr int R = 25000;
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;
    }
};

static int h[N], p[N], f[R], in[N], out[N];
static vector<int> fi(R, -1), ff;
static vector<int> adj[N];
static vector<int> vs[R];
vector<vector<LL>> sub, anc;

int t = 0;
static void dfs0(int v) {
    in[v] = t++;
    for (int u : adj[v]) {
        dfs0(u);
    }
    out[v] = t;
}

static int dfs1(int v, const int i, int acc = 0) {
    int cnt = 0;
    for (int u : adj[v]) {
        cnt += dfs1(u, i, acc + (h[v] == ff[i]));
    }
    sub[h[v]][i] += cnt;
    anc[h[v]][i] += acc;
    return cnt + (h[v] == ff[i]);
}

int main() {
    int n; cin >> n;
    int r; cin >> r;
    int q; cin >> q;
    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]];
    }
    for (int i = 0; i < r; ++i) {
        if (f[i] >= SQ) {
            fi[i] = ff.size();
            ff.push_back(i);
        }
    }

    dfs0(0);

    for (int v = 0; v < n; ++v) {
        vs[h[v]].push_back(v);
    }

    sub.assign(r, vector<LL>(ff.size()));
    anc.assign(r, vector<LL>(ff.size()));
    for (int i = 0; i < (int)ff.size(); ++i) {
        dfs1(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 3 ms 5584 KB Output is correct
2 Correct 4 ms 5712 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 8 ms 5712 KB Output is correct
5 Correct 6 ms 5712 KB Output is correct
6 Correct 21 ms 5712 KB Output is correct
7 Correct 34 ms 5712 KB Output is correct
8 Correct 34 ms 5840 KB Output is correct
9 Correct 56 ms 6096 KB Output is correct
10 Correct 98 ms 6316 KB Output is correct
11 Correct 164 ms 6588 KB Output is correct
12 Correct 189 ms 7072 KB Output is correct
13 Correct 209 ms 6864 KB Output is correct
14 Correct 310 ms 7416 KB Output is correct
15 Correct 631 ms 9168 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 11460 KB Output is correct
2 Correct 1540 ms 9872 KB Output is correct
3 Correct 4180 ms 14396 KB Output is correct
4 Correct 277 ms 7584 KB Output is correct
5 Correct 492 ms 8912 KB Output is correct
6 Correct 689 ms 16296 KB Output is correct
7 Correct 1559 ms 16352 KB Output is correct
8 Correct 1511 ms 34788 KB Output is correct
9 Correct 4354 ms 16068 KB Output is correct
10 Correct 4153 ms 65992 KB Output is correct
11 Correct 5966 ms 16992 KB Output is correct
12 Correct 2065 ms 19360 KB Output is correct
13 Correct 2722 ms 20288 KB Output is correct
14 Correct 3264 ms 26192 KB Output is correct
15 Correct 5538 ms 27532 KB Output is correct
16 Correct 6058 ms 38740 KB Output is correct
17 Correct 5029 ms 42108 KB Output is correct