oj.uz

Submission #738928

# Submission time Handle Problem Language Result Execution time Memory
738928 2023-05-09T16:35:19 Z lorenzoferrari Regions (IOI09_regions) C++17
70 / 100
 6366 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 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];
static LL sub[R][N / SQ];
static LL anc[R][N / SQ];

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);
    }

    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 5 ms 7248 KB Output is correct
2 Correct 4 ms 7248 KB Output is correct
3 Correct 6 ms 7248 KB Output is correct
4 Correct 12 ms 7248 KB Output is correct
5 Correct 12 ms 7248 KB Output is correct
6 Correct 21 ms 7248 KB Output is correct
7 Correct 34 ms 7248 KB Output is correct
8 Correct 42 ms 7376 KB Output is correct
9 Correct 73 ms 7668 KB Output is correct
10 Correct 133 ms 7760 KB Output is correct
11 Correct 158 ms 8016 KB Output is correct
12 Correct 226 ms 8392 KB Output is correct
13 Correct 232 ms 8248 KB Output is correct
14 Correct 413 ms 8776 KB Output is correct
15 Correct 609 ms 10404 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1920 ms 14132 KB Output is correct
2 Correct 1496 ms 12500 KB Output is correct
3 Correct 4387 ms 17380 KB Output is correct
4 Correct 408 ms 8724 KB Output is correct
5 Correct 562 ms 9848 KB Output is correct
6 Correct 721 ms 64868 KB Output is correct
7 Correct 1460 ms 96740 KB Output is correct
8 Correct 1501 ms 108528 KB Output is correct
9 Correct 4948 ms 15736 KB Output is correct
10 Runtime error 157 ms 131072 KB Execution killed with signal 9
11 Correct 6366 ms 15708 KB Output is correct
12 Correct 1904 ms 130964 KB Output is correct
13 Runtime error 207 ms 131072 KB Execution killed with signal 9
14 Runtime error 217 ms 131072 KB Execution killed with signal 9
15 Runtime error 201 ms 131072 KB Execution killed with signal 9
16 Runtime error 188 ms 131072 KB Execution killed with signal 9
17 Runtime error 170 ms 131072 KB Execution killed with signal 9