oj.uz

Submission #738959

# Submission time Handle Problem Language Result Execution time Memory
738959 2023-05-09T17:35:39 Z lorenzoferrari Regions (IOI09_regions) C++17
100 / 100
 2326 ms 45136 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 = 700;

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<array<int, 2>> ev[R];
static vector<array<int, 2>> 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({in[v], v});
        ev[h[v]].push_back({in[v], +1});
        ev[h[v]].push_back({out[v],-1});
    }
    for (int i = 0; i < r; ++i) {
        sort(begin(ev[i]), end(ev[i]));
        sort(begin(vs[i]), end(vs[i]));
    }

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

    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;
            int j = 0, act = 0;
            for (auto [tin, v] : vs[r2]) {
                while (j != (int)ev[r1].size() && ev[r1][j][0] <= tin) {
                    act += ev[r1][j][1];
                    ++j;
                }
                ans += act;
            }
            cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6224 KB Output is correct
2 Correct 5 ms 6224 KB Output is correct
3 Correct 8 ms 6224 KB Output is correct
4 Correct 9 ms 6224 KB Output is correct
5 Correct 12 ms 6224 KB Output is correct
6 Correct 23 ms 6352 KB Output is correct
7 Correct 28 ms 6352 KB Output is correct
8 Correct 30 ms 6480 KB Output is correct
9 Correct 53 ms 6888 KB Output is correct
10 Correct 86 ms 7068 KB Output is correct
11 Correct 99 ms 7524 KB Output is correct
12 Correct 126 ms 8144 KB Output is correct
13 Correct 179 ms 7992 KB Output is correct
14 Correct 203 ms 8836 KB Output is correct
15 Correct 232 ms 10740 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 13548 KB Output is correct
2 Correct 1084 ms 11856 KB Output is correct
3 Correct 1388 ms 16668 KB Output is correct
4 Correct 280 ms 8880 KB Output is correct
5 Correct 348 ms 10056 KB Output is correct
6 Correct 702 ms 10620 KB Output is correct
7 Correct 985 ms 12460 KB Output is correct
8 Correct 998 ms 16504 KB Output is correct
9 Correct 1309 ms 20384 KB Output is correct
10 Correct 2158 ms 23592 KB Output is correct
11 Correct 2326 ms 21624 KB Output is correct
12 Correct 975 ms 23096 KB Output is correct
13 Correct 1310 ms 24040 KB Output is correct
14 Correct 2113 ms 28620 KB Output is correct
15 Correct 2011 ms 31452 KB Output is correct
16 Correct 2091 ms 42028 KB Output is correct
17 Correct 2175 ms 45136 KB Output is correct