Submission #957158

#	Time	Username	Problem	Language	Result	Execution time	Memory
957158		ZHIRDILBILDIZ	Tourism (JOI23_tourism)	C++14	100 / 100	589 ms	38860 KiB

tourism

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = (1 << 17);
int c[N];
int sum[N << 1 ^ 1];
vector<int> gr[N];
vector<pii> qr[N];
///segment_tree begin
void upd_point_seg_tree (int ind, int vall) {
    ind += N - 1;
    sum[ind] += vall;
    ind >>= 1;
    while (ind) {
        sum[ind] = sum[ind << 1] + sum[ind << 1 ^ 1];
        ind >>= 1;
    }
}
int get_sum(int l1, int r1, int l = 1, int r = N, int v = 1) {
    if (l > r1 || r < l1)
        return 0;
    if (l1 <= l && r <= r1)
        return sum[v];
    int mid = (l + r) >> 1;
    return get_sum(l1, r1, l, mid, v << 1) + get_sum(l1, r1, mid + 1, r, v << 1 ^ 1);
}
///segment_tree end

///build_compose begin
int pos[N];
int pr[N];
int big[N];
int head[N];
int tin[N];
int tout[N];
int timer;
int lc[N][20];
vector<int> tr;
bool upper(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int pre_calc (int city = 1, int last = 0) {
    tin[city] = ++timer;
    int cnt = 1;
    pii mx = {0, 0};
    for (int i : gr[city]) {
        if (i == last)
            continue;
        int w = pre_calc(i, city);
        mx = max(mx, {w, i});
        cnt += w;
    }
    tout[city] = ++timer;
    big[city] = mx.se;
    return cnt;
}
void dfs (int city = 1, int last = 0, int h = 1) {
    pr[city] = last;
    lc[city][0] = last;
    for (int i = 1; i < 20; ++i)
        lc[city][i] = lc[lc[city][i - 1]][i - 1];
    head[city] = h;
    pos[city] = tr.size();
    tr.push_back(city);
    if (big[city])
        dfs(big[city], city, h);
    for (int i : gr[city]) {
        if (i == last || i == big[city])
            continue;
        dfs(i, city, i);
    }
}
///build_compose end

///query and update on decompose begin
int color[2 * N + 1];
bool have[2 * N + 1];
void tractor (int v) {
    have[v] = (color[v] > 0);
    if (v < N && (have[v << 1] || have[v << 1 ^ 1]))
        have[v] = 1;
}
void push (int v) {
    if (!color[v] || v >= N)
        return;
    int x = color[v];
    color[v] = 0;
    color[v << 1] = x;
    color[v << 1 ^ 1] = x;
    tractor(v << 1);
    tractor(v << 1 ^ 1);
}
void set_color (int l, int r, int v, int x) {
    if (color[v])
        upd_point_seg_tree(color[v], -(r - l + 1));
    color[v] = x;
    if (color[v])
        upd_point_seg_tree(color[v], (r - l + 1));
    tractor(v);
}
void mega_clear (int l, int r, int v) {
    set_color (l, r, v, 0);
    if (!have[v])
        return;
    int mid = (l + r) >> 1;
    mega_clear (l, mid, v << 1);
    mega_clear (mid + 1, r, v << 1 ^ 1);
    have[v] = 0;
}
void update (int l1, int r1, int x, int l = 0, int r = N - 1, int v = 1) {
    if (l > r1 || r < l1)
        return;
    if (l1 <= l && r <= r1) {
        mega_clear(l, r, v);
        set_color(l, r, v, x);
        return;
    }
    push(v);
    int mid = (l + r) >> 1;
    update(l1, r1, x, l, mid, v << 1);
    update(l1, r1, x, mid + 1, r, v << 1 ^ 1);
    tractor(v);
}

int get_lca(int u, int v) {
    if (upper(u, v))
        return u;
    if (upper(v, u))
        return v;
    for (int i = 19; i >= 0; --i)
        if (lc[u][i] && !upper(lc[u][i], v))
            u = lc[u][i];
    return pr[u];
}

void update_on_path (int u, int v, int x) {
    int lc = get_lca(u, v);
//    cout << "update_on_path " << u << ' ' << v << ' ' << lc << ' ' << x << '\n';
    while (u != pr[lc]) {
        if (!upper(head[u], lc)) {
            update(pos[head[u]], pos[u], x);
//            cout << "sum1 = " << pos[head[u]] << ' ' << pos[u] << ' ' << get_sum(4, 6) << '\n';
            u = pr[head[u]];
        } else {
            update(pos[lc], pos[u], x);
//            cout << "sum2 = " << pos[lc] << ' ' << pos[u] << ' ' << get_sum(4, 6) << '\n';
            u = pr[lc];
        }
    }
    while (v != pr[lc])
        if (!upper(head[v], lc)) {
            update(pos[head[v]], pos[v], x);
//            cout << "sum3 = " << pos[head[v]] << ' ' << pos[v] << ' ' << get_sum(4, 6) << '\n';
            v = pr[head[v]];
        } else {
            update(pos[lc], pos[v], x);
//            cout << "sum4 = " << pos[lc] << ' ' << pos[v] << ' ' << get_sum(4, 6) << '\n';
            v = pr[lc];
        }
}
///query and update on decompose end

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    for (int i = 1; i <= m; ++i)
        cin >> c[i];

    int ans[q + 1] = {};
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        if (l == r) {
            ans[i] = 1;
            continue;
        }
        qr[r].push_back({l, i});
    }
    pre_calc();
    dfs();

    for (int i = 2; i <= m; ++i) {
        update_on_path (c[i - 1], c[i], i - 1);
//        cout << "after update_on_path " << c[i - 1] << ' ' << c[i] << ' ' << i - 1 << " " << get_sum(4, 6) << '\n';
//        cout << "_______________________________________________\n";
        for (auto j : qr[i])
            ans[j.se] = get_sum(j.fi, i);
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41