Submission #1124581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124581		macneil	Tourism (JOI23_tourism)	C++20	18 / 100	634 ms	41460 KiB

tourism

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>

using namespace std;

#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long long ll;
typedef long double ld;

struct SegTree {
    vector<int> szs;
    vector<pair<int, int>> tr;
    vector<int> lol;
    int sz;

    SegTree(){}

    void build(int n) {
        sz = (1 << ((int)log2(n))) * 2;
        lol.resize(4 * sz, -1);
        tr.resize(sz * 2, {1e9, 1e9});
        szs.resize(sz * 2);
        for (int i = 0; i < n; ++i) szs[sz - 1 + i] = 1;
        for (int i = sz - 2; i >= 0; --i) szs[i] = szs[i * 2 + 1] + szs[i * 2 + 2];
    }

    void push(int v) {
        if (lol[v] == -1) return;
        tr[v] = {lol[v], lol[v]};
        if (2 * v + 2 < 2 * sz) {
            lol[2 * v + 1] = lol[v];
            lol[2 * v + 2] = lol[v];
        }
        lol[v] = -1;
    }

    pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
        return {min(a.first, b.first), max(a.second, b.second)};
    }

    void update(int v, int l, int r, int ql, int qr, int x) {
        push(v);
        if (ql >= r || qr <= l) return;
        if (l >= ql && r <= qr) {
            lol[v] = x;
            push(v);
            return;
        }
        int m = (l + r) / 2;
        update(2 * v + 1, l, m, ql, qr, x);
        update(2 * v + 2, m, r, ql, qr, x);
        tr[v] = merge(tr[2 * v + 1], tr[2 * v + 2]);
    }

    void update(int l, int r, int x) {
        update(0, 0, sz, l, r, x);
    }

    int get(int v, int l, int r, int x) {
        push(v);
        if (tr[v].first >= x) return 0;
        if (tr[v].second < x) return r - l;
        if (r - l == 0) return 0;
        int m = (l + r) / 2;
        return get(v * 2 + 1, l, m, x) + get(v * 2 + 2, m, r, x);
    }

    int get(int x) {
        return get(0, 0, sz, x);
    }
};

vector<int> sz, upto, tin, tout, ord, backord;
vector<vector<int>> p, gr;
SegTree lol;
int timer = 0;

void dfssize(int v, int pr) {
    p[0][v] = pr;
    for (int i = 1; i < 20; ++i) p[i][v] = p[i - 1][p[i - 1][v]];
    tin[v] = timer++;
    sz[v] = 1;
    for (auto e : gr[v]) {
        if (e == pr) continue;
        dfssize(e, v);
        sz[v] += sz[e];
    }
    tout[v] = timer++;
}

void dfsreorder(int v, int pr) {
    backord[v] = ord.size();
    ord.push_back(v);
    if (upto[v] == -1) upto[v] = v;
    if (gr[v].size() == 1 && pr != -1) return;
    if (gr[v][0] == pr) swap(gr[v][0], gr[v][1]);
    for (auto &e : gr[v]) {
        if (e == pr) continue;
        if (sz[e] > sz[gr[v][0]]) swap(e, gr[v][0]);
    }
    upto[gr[v][0]] = upto[v];
    for (auto e : gr[v]) {
        if (e == pr) continue;
        dfsreorder(e, v);
    }
}

bool isanc(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if (isanc(a, b)) return a;
    if (isanc(b, a)) return b;
    for (int i = 19; i >= 0; --i) {
        if (!isanc(p[i][a], b)) a = p[i][a];
    }
    return p[0][a];
}

void update(int a, int b, int ind) {
    int c = lca(a, b);
    while (1) {
        int t = upto[a];
        if (isanc(t, c)) t = c;
        lol.update(backord[t], backord[a] + 1, ind);
        if (t == c) break;
        a = p[0][t];
    }
    while (1) {
        int t = upto[b];
        if (isanc(t, c)) t = c;
        lol.update(backord[t], backord[b] + 1, ind);
        if (t == c) break;
        b = p[0][t];
    }
}

int get(int x) {
    return lol.get(x);
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    upto.resize(n, -1);
    sz.resize(n);
    tin.resize(n);
    tout.resize(n);
    backord.resize(n);
    p.resize(20, vector<int>(n));
    gr.resize(n);
    lol.build(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    dfssize(0, 0);
    dfsreorder(0, -1);
    vector<int> lolkek(m);
    for (int i = 0; i < m; ++i) {
        cin >> lolkek[i];
        lolkek[i]--;
    }
    vector<int> ans(q);
    vector<vector<pair<int, int>>> qs(m);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        if (l == r) {
            ans[i] = 1;
            continue;
        }
        qs[l - 1].push_back({r, i});
    }
    for (int i = m - 2; i >= 0; --i) {
        update(lolkek[i], lolkek[i + 1], i + 1);
        for (auto e : qs[i]) {
            ans[e.second] = get(e.first);
        }
    }
    for (auto e : ans) cout << e << '\n';
}

signed main() {
    int tc = 1;
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#endif
    // int g; cin >> g;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

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