Submission #896342

#	Time	Username	Problem	Language	Result	Execution time	Memory
896342		CDuong	Tourism (JOI23_tourism)	C++17	100 / 100	577 ms	25004 KiB

tourism

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 1e5 + 5;
const int mxM = 1e5 + 5;
const int mxQ = 1e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

struct FenwickTree {
    int n;
    vector<int> data;

    FenwickTree(int n) : n(n), data(n + 1) {}

    void update(int idx, int val) {
        // cout << idx << " " << val << "\n";
        for (; idx <= n; idx += idx & -idx)
            data[idx] += val;
    }

    int get(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res += data[idx];
        return res;
    }
};

vector<int> G[mxN];
int n, m, q, ss[mxM];
vector<pair<int, int>> queries[mxQ];
int ans[mxQ];

int tdfs, sz[mxN], tin[mxN], head[mxN], tout[mxN], par[mxN], dep[mxN];
set<pair<int, int>> s;

void dfs(int v, int p) {
    sz[v] = 1;
    for (int &u : G[v]) if (u != p) {
        dfs(u, v);
        if (G[v][0] == p or sz[u] > sz[G[v][0]])
            swap(u, G[v][0]);
    }
}

void dfs_hld(int v, int p, int top) {
    tin[v] = ++tdfs;
    head[v] = top;
    par[v] = p;
    dep[v] = dep[p] + 1;

    if (not G[v].empty() and G[v][0] != p)
        dfs_hld(G[v][0], v, top);

    for (int i = 1; i < isz(G[v]); ++i) if (G[v][i] != p)
        dfs_hld(G[v][i], v, G[v][i]);

    tout[v] = tdfs;
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> ss[i];
    }
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        queries[l].emplace_back(r, i);
    }

    dfs(1, 0);
    dfs_hld(1, 0, 1);

    FenwickTree fenw(m + 1);
    s.insert({2, m + 1}); s.insert({n + 1, -1}); fenw.update(m + 1, n - 1);

    auto del = [&](int l, int r) -> void {
        // cout << l << " -> " << r << endl;
        auto it = prev(s.upper_bound({l, INT_MAX}));
        do {
            // assert(it != s.end());
            int cl = it->ff, cr = next(it)->ff - 1, val = it->ss, len = min(cr, r) - max(cl, l) + 1;
            // cout << len << endl;
            it = s.erase(it);
            if (cl < l) s.insert({cl, val});
            if (r < cr) s.insert({r + 1, val});
            fenw.update(val, -len);
        } while (it->ff <= r);
        // cout << endl;
    };

    auto add = [&](int l, int r, int val) -> void {
        fenw.update(val, r - l + 1);
        s.insert({l, val});
        // cout << endl;
    };

    auto update_hld = [&](int u, int v, int val) -> void {
        // cout << u << " " << v << " " << val << endl;
        while (head[u] != head[v]) {
            // cout << head[u] << " " << head[v] << endl;
            if (dep[head[u]] < dep[head[v]])
                swap(u, v);
            // tin[head[u]] -> tin[u]
            del(tin[head[u]], tin[u]);
            add(tin[head[u]], tin[u], val);
            u = par[head[u]];
        }
        if (u != v) {
            if (dep[u] > dep[v]) swap(u, v);
            // tin[u] + 1 -> tin[v]
            del(tin[u] + 1, tin[v]);
            add(tin[u] + 1, tin[v], val);
        }
    };

    for (int L = m; L >= 1; --L) {
        // cout << L << endl;
        if (L != m) update_hld(ss[L], ss[L + 1], L + 1);
        for (auto [R, idx] : queries[L]) {
            ans[idx] = fenw.get(R) + 1;
            // cout << idx << " " << fenw.get(R) + 1 << "\n";
        }
    }

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

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

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