oj.uz

Submission #158061

# Submission time Handle Problem Language Result Execution time Memory
158061 2019-10-14T14:56:28 Z darkkcyan Regions (IOI09_regions) C++17
100 / 100
 3022 ms 51684 KB 
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

const int maxn = 201010;
const int root = 1;
const int threshold = 500;
int n, r, q;
int h[maxn];
vector<int> gr[maxn];

int cnt_h[maxn] = {0};
vector<llong> pre_comp_ans1[maxn], pre_comp_ans2[maxn];

int dfs_cal_heavy(int u, int cur_heavy, int cnt_heavy_up) {
    pre_comp_ans1[cur_heavy][h[u]] += cnt_heavy_up;
    cnt_heavy_up += h[u] == cur_heavy;
    int cnt_heavy_down = 0;
    for (auto v: gr[u]) {
        cnt_heavy_down += dfs_cal_heavy(v, cur_heavy, cnt_heavy_up);
    }
    pre_comp_ans2[cur_heavy][h[u]] += cnt_heavy_down;
    cnt_heavy_down += h[u] == cur_heavy;
    return cnt_heavy_down;
}

int eu_tour_start[maxn], eu_tour_end[maxn], cur_tour = 0;
vector<pair<int, int>> euler_tours[maxn];

void dfs_cal_light(int u) {
    bool is_light = cnt_h[h[u]] <= threshold;
    if (is_light) { 
        euler_tours[h[u]].emplace_back(
            euler_tours[h[u]].size() ? euler_tours[h[u]].back().xx + 1 : 1,
            cur_tour
        );
        eu_tour_start[u] = cur_tour++;
    }

    for (auto v: gr[u]) {
        dfs_cal_light(v);
    }

    if (is_light) {
        euler_tours[h[u]].emplace_back(
            euler_tours[h[u]].back().xx - 1,
            cur_tour
        );
        eu_tour_end[u] = cur_tour++;
    }
}


int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> r >> q;
    cin >> h[1];
    for (int i = 2; i <= n; ++i) {
        int s; 
        cin >> s >> h[i];
        gr[s].push_back(i);
    }

    rep1(i, n) cnt_h[h[i]]++;
    rep1(i, r) if (cnt_h[i] > threshold) {
        pre_comp_ans1[i].resize(r + 1);
        pre_comp_ans2[i].resize(r + 1);
        dfs_cal_heavy(root, i, 0);
    }

    dfs_cal_light(root);
    while (q--) {
        int r1, r2; cin >> r1 >> r2;
        if (cnt_h[r1] > threshold) {
            cout << pre_comp_ans1[r1][r2] << endl;
            continue;
        }
        if (cnt_h[r2] > threshold) {
            cout << pre_comp_ans2[r2][r1] << endl;
            continue;
        }

        llong ans = 0;
        int u = 0, v = 0;
        for (; v < len(euler_tours[r2]); ++v) {
            if (v and euler_tours[r2][v].xx < euler_tours[r2][v - 1].xx) continue;
            while (u < len(euler_tours[r1]) and euler_tours[r1][u].yy < euler_tours[r2][v].yy)
                ++u;
            if (u) ans += euler_tours[r1][u - 1].xx;
        }
        cout << ans << endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 22 ms 19192 KB Output is correct
4 Correct 25 ms 19192 KB Output is correct
5 Correct 27 ms 19192 KB Output is correct
6 Correct 40 ms 19320 KB Output is correct
7 Correct 53 ms 19320 KB Output is correct
8 Correct 62 ms 19320 KB Output is correct
9 Correct 70 ms 19896 KB Output is correct
10 Correct 84 ms 19872 KB Output is correct
11 Correct 102 ms 20252 KB Output is correct
12 Correct 141 ms 20856 KB Output is correct
13 Correct 191 ms 20588 KB Output is correct
14 Correct 238 ms 21160 KB Output is correct
15 Correct 272 ms 24440 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 24452 KB Output is correct
2 Correct 845 ms 23032 KB Output is correct
3 Correct 1763 ms 26972 KB Output is correct
4 Correct 280 ms 21356 KB Output is correct
5 Correct 357 ms 23272 KB Output is correct
6 Correct 867 ms 22636 KB Output is correct
7 Correct 1253 ms 23800 KB Output is correct
8 Correct 1121 ms 29936 KB Output is correct
9 Correct 2023 ms 30712 KB Output is correct
10 Correct 2524 ms 35992 KB Output is correct
11 Correct 3022 ms 30360 KB Output is correct
12 Correct 1293 ms 31680 KB Output is correct
13 Correct 1632 ms 32272 KB Output is correct
14 Correct 2224 ms 37724 KB Output is correct
15 Correct 2534 ms 37948 KB Output is correct
16 Correct 2698 ms 46984 KB Output is correct
17 Correct 2340 ms 51684 KB Output is correct