Submission #986930

#	Time	Username	Problem	Language	Result	Execution time	Memory
986930		876pol	Tourism (JOI23_tourism)	C++17	35 / 100	5008 ms	77280 KiB

tourism

#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()

#define MOD 1000000007
// #define MOD 998244353

#define FASTIO
#define PRECISION
// #define FILE "file"

#define SINGLE
// #define MULTIPLE
// #define GOOGLE

void solve() {
    ll n, m, q;
    cin >> n >> m >> q;
    bool st3 = true;
    vvll graph(n + 1);
    FOR(i, 0, n - 1) {
        ll a, b;
        cin >> a >> b;
        st3 &= (a + 1 == b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    if (st3) {
        vll c(m + 1);
        CFOR(i, 1, m) cin >> c[i];
        ll L = 20;
        vvll stmn(L, vll(m + 1)), stmx(L, vll(m + 1));
        CFOR(i, 1, m) stmn[0][i] = stmx[0][i] = c[i];
        FOR(i, 1, L) {
            CFOR(j, 1, m + 1 - (1ll << i)) {
                stmn[i][j] =
                    min(stmn[i - 1][j], stmn[i - 1][j + (1ll << (i - 1))]);
                stmx[i][j] =
                    max(stmx[i - 1][j], stmx[i - 1][j + (1ll << (i - 1))]);
            }
        }
        auto qmn = [&](ll l, ll r) {
            ll q = 63 - __builtin_clzll(r - l + 1);
            return min(stmn[q][l], stmn[q][r - (1ll << q) + 1]);
        };
        auto qmx = [&](ll l, ll r) {
            ll q = 63 - __builtin_clzll(r - l + 1);
            return max(stmx[q][l], stmx[q][r - (1ll << q) + 1]);
        };
        FOR(_, 0, q) {
            ll l, r;
            cin >> l >> r;
            cout << qmx(l, r) - qmn(l, r) + 1 << "\n";
        }
    } else {
        vll euler, dist, tin(n + 1), level(n + 1);
        ll cdist = 0;
        function<void(ll, ll)> dfs1 = [&](ll curr, ll prev) {
            tin[curr] = euler.size();
            level[curr] = cdist;
            euler.push_back(curr);
            dist.push_back(cdist);
            cdist++;
            TRAV(e, graph[curr]) {
                if (e == prev) continue;
                dfs1(e, curr);
                euler.push_back(curr);
                dist.push_back(cdist - 1);
            }
            cdist--;
        };
        dfs1(1, 0);
        ll L = 20;
        vvpll st(L, vpll(euler.size()));
        FOR(i, 0, euler.size()) st[0][i] = {dist[i], euler[i]};
        FOR(i, 1, L) {
            CFOR(j, 0, euler.size() - (1ll << i)) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1ll << (i - 1))]);
            }
        }
        auto lca = [&](ll x, ll y) {
            x = tin[x];
            y = tin[y];
            if (x > y) swap(x, y);
            ll q = 63 - __builtin_clzll(y - x + 1);
            return min(st[q][x], st[q][y - (1ll << q) + 1]).second;
        };
        auto ds = [&](ll x, ll y) {
            return level[x] + level[y] - 2 * level[lca(x, y)];
        };
        vll c(m + 1);
        CFOR(i, 1, m) cin >> c[i];
        FOR(_, 0, q) {
            ll l, r;
            cin >> l >> r;
            vll nodes;
            nodes.reserve(r - l + 2);
            ll root = c[l];
            CFOR(i, l, r) {
                nodes.push_back(c[i]);
                root = lca(root, c[i]);
            }
            nodes.push_back(root);
            sort(all(nodes));
            nodes.erase(unique(all(nodes)), nodes.end());
            sort(all(nodes), [&](ll o1, ll o2) { return tin[o1] < tin[o2]; });
            vll stk = {root};
            ll ans = 1;
            for (auto it = nodes.begin() + 1; it != nodes.end(); it++) {
                vll tr;
                while (lca(stk.back(), *it) != stk.back()) {
                    tr.push_back(stk.back());
                    stk.pop_back();
                }
                if (tr.size() && stk.back() != lca(*it, tr.back())) {
                    stk.push_back(lca(*it, tr.back()));
                }
                FOR(i, 0, tr.size() - 1) {
                    ans += ds(tr[i], tr[i + 1]);
                }
                if (tr.size()) ans += ds(tr.back(), stk.back());
                stk.push_back(*it);
            }
            FOR(i, 0, stk.size() - 1) {
                ans += ds(stk[i], stk[i + 1]);
            }
            cout << ans << "\n";
        }
    }
}

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#endif
#ifdef PRECISION
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
#endif
#ifdef FILE
    freopen((FILE + string(".in")).c_str(), "r", stdin);
    freopen((FILE + string(".out")).c_str(), "w", stdout);
#endif
#ifdef SINGLE
    solve();
#endif
#ifdef MULTIPLE
    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        solve();
    }
#endif
#ifdef GOOGLE
    ll t;
    cin >> t;
    for (ll i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
#endif
}

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