제출 #938983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938983		juliany2	Tourism (JOI23_tourism)	C++17	100 / 100	922 ms	32904 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<class T> struct BIT {
    int n;
    vector<T> bit;

    void init(int sz) { bit = vector<T> (n = sz + 7); }

    void upd(int i, T x) { 
        for (i++; i < n; i += i & -i) bit[i] += x;
    }

    T query(int i) {
        T ret = 0;
        for (i++; i > 0; i -= i & -i) ret += bit[i];
        return ret;
    }

    T query(int l, int r) { return query(r) - query(l - 1); };
};

const int N = 1e5 + 7, L = 20;
int n, m, q;
int c[N];
int lift[N][L], dep[N], sz[N], ans[N];
int head[N], pos[N], timer;
vector<int> adj[N];
vector<array<int, 2>> ask[N];
set<array<int, 3>> s;
BIT<int> bit;

void dfs(int v = 1, int p = 0) {
    sz[v] = 1;
    lift[v][0] = p;
    for (int i = 1; i < L; i++)
        lift[v][i] = lift[lift[v][i - 1]][i - 1];

    for (int &u : adj[v]) {
        if (u != p) {
            dep[u] = dep[v] + 1;
            dfs(u, v);

            sz[v] += sz[u];
            if (adj[v][0] == p || sz[u] > sz[adj[v][0]])
                swap(u, adj[v][0]);
        }
    }
}

void dfs_hld(int v = 1, int p = 0) {
    pos[v] = ++timer;
    for (int u : adj[v]) {
        if (u != p) {
            head[u] = (u == adj[v][0] ? head[v] : u);
            dfs_hld(u, v);
        }
    }
}

void add(int l, int r, int x) {
    array<int, 3> comp = {l, -1, -1};
    while (s.lower_bound(comp) != s.end() && (*s.lower_bound(comp))[0] <= r) {
        auto [a, b, y] = *s.lower_bound({l, -1, -1});
        if (b <= r) {
            bit.upd(y, -(b - a + 1));
            s.erase({a, b, y});
        }
        else {
            bit.upd(y, -(r - a + 1));
            s.insert({r + 1, b, y});
            s.erase({a, b, y});
        }
    }

    bit.upd(x, r - l + 1);
    s.insert({l, r, x});
}

void query(int v, int x) {
    for (; v > 0; v = lift[head[v]][0])
        add(pos[head[v]], pos[v], x);
}

int lca(int u, int v) {
    if (u == 0 || v == 0)
        return max(u, v);
    if (dep[u] > dep[v])
        swap(u, v);

    for (int i = L - 1; ~i; --i)
        if (dep[v] - (1 << i) >= dep[u])
            v = lift[v][i];

    if (u == v)
        return u;

    for (int i = L - 1; ~i; --i)
        if (lift[v][i] != lift[u][i])
            v = lift[v][i], u = lift[u][i];
    return lift[u][0];
}

template<class T> struct ST_LCA {
    static constexpr T ID = 0; // or whatever ID
    inline T comb(T a, T b) { return lca(a, b); } // or whatever function

    int sz;
    vector<T> t;

    void init(int _sz, T val = ID) {
        t.assign((sz = _sz) * 2, ID);
    }
    void init(vector<T> &v) {
        t.resize((sz = v.size()) * 2);
        for (int i = 0; i < sz; ++i)
            t[i + sz] = v[i];
        for (int i = sz - 1; i; --i)
            t[i] = comb(t[i * 2], t[(i * 2) | 1]);
    }
    void upd(int i, T x) {
        for (t[i += sz] = x; i > 1; i >>= 1)
            t[i >> 1] = comb(t[i], t[i ^ 1]);
    }
    T query(int l, int r) {
        T ql = ID, qr = ID;
        for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ql = comb(ql, t[l++]);
            if (r & 1) qr = comb(t[--r], qr);
        }
        return comb(ql, qr);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> q;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= m; i++)
        cin >> c[i];

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;

        ask[l].push_back({r, i});
    }

    dfs();

    head[1] = 1;

    dfs_hld();

    ST_LCA<int> lcas;
    lcas.init(m + 1);
    for (int i = 1; i <= m; i++)
        lcas.upd(i, c[i]);

    bit.init(m + 1);

    for (int i = m; i >= 1; i--) {
        query(c[i], i);

        for (auto &[j, idx] : ask[i])
            ans[idx] = bit.query(i, j) - dep[lcas.query(i, j)];
    }

    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