제출 #1032630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032630		adaawf	Tourism (JOI23_tourism)	C++17	100 / 100	505 ms	32344 KiB

tourism

#include <iostream>
#include <vector>
using namespace std;
vector<int> g[100005];
vector<pair<int, int>> v[100005];
int a[100005], s[100005], d[100005], l[100005][18], pp[100005];
int dd[100005], res[100005], z = 0, h = 2000, c[120005], cc[120005], t[400005];
void dfs(int x, int p) {
    l[x][0] = p;
    s[x] = 1;
    for (int w : g[x]) {
        if (w == p) continue;
        d[w] = d[x] + 1;
        dfs(w, x);
        s[x] += s[w];
    }
    for (int &w : g[x]) {
        if (w == p) continue;
        if (s[w] >= (s[x] + 1) / 2) {
            swap(w, g[x][0]);
        }
    }
}
void dfshld(int x, int p, int h, int flag) {
    dd[x] = ++z;
    pp[x] = h;
    for (int w : g[x]) {
        if (w == p) continue;
        if (s[w] >= (s[x] + 1) / 2) {
            if (flag == 0) h = w;
            dfshld(w, x, h, 1);
        }
        else dfshld(w, x, w, 0);
    }
}
int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    int k = d[x] - d[y];
    for (int i = 17; i >= 0; i--) {
        if (k & (1 << i)) {
            x = l[x][i];
        }
    }
    if (x == y) return x;
    for (int i = 17; i >= 0; i--) {
        if (l[x][i] != l[y][i]) {
            x = l[x][i];
            y = l[y][i];
        }
    }
    return l[x][0];
}
int rise(int x, int y) {
    for (int i = 0; i <= 17; i++) {
        if (y & (1 << i)) {
            x = l[x][i];
        }
    }
    return x;
}
void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        if (t[v] != -1) {
            //cout << l << " " << r << " " << t[v] << " " << x << '\n';
            c[t[v] / h] -= r - l + 1;
            cc[t[v]] -= r - l + 1;
            t[v] = x;
            c[t[v] / h] += r - l + 1;
            cc[t[v]] += r - l + 1;
            return;
        }
        if (l == r) return;
    }
    if (t[v] != -1) {
        t[v * 2] = t[v * 2 + 1] = t[v];
    }
    int mid = (tl + tr) / 2;
    update(v * 2, tl, mid, l, min(r, mid), x);
    update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
    if (t[v * 2] == -1 || t[v * 2 + 1] == -1) t[v] = -1;
    else if (t[v * 2] == t[v * 2 + 1]) t[v] = t[v * 2];
    else t[v] = -1;
}
void hld(int x, int y, int c) {
    int h = lca(x, y);
    while (x != h || y != h) {
        if (d[x] < d[y]) swap(x, y);
        int k = pp[x];
        if (d[k] <= d[h]) {
            k = rise(x, d[x] - d[h] - 1);
        }
        //cout << x << " " << y << " " << h << " " << k << " " << dd[k] << " " << dd[x] << " " << c << '\n';
        update(1, 1, z, dd[k], dd[x], c);
        x = l[k][0];
    }
}
int main() {
    ios::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;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    cc[0] = c[0] = n;
    dfs(1, 0);
    dfshld(1, 0, 0, 0);
    for (int i = 1; i <= 17; i++) {
        for (int j = 1; j <= n; j++) {
            l[j][i] = l[l[j][i - 1]][i - 1];
        }
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        v[r].push_back({l, i});
        if (r == 1) res[i] = 1;
    }
    for (int i = 2; i <= m; i++) {
        hld(a[i], a[i - 1], i - 1);
        for (auto w : v[i]) {
            int l = w.first, ll = 0;
            for (int j = m / h; j > l / h; j--) ll += c[j];
            for (int j = l; j < min((l / h + 1) * h, m); j++) ll += cc[j];
            res[w.second] = ll + 1;
            //for (int j = 0; j < n; j++) cout << cc[j] << " ";
            //cout << '\n';
        }
    }
    for (int i = 0; i < q; i++) cout << res[i] << '\n';
}

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