제출 #953080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953080		arbuzick	Tourism (JOI23_tourism)	C++17	100 / 100	2919 ms	174912 KiB

tourism

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")

using namespace std;

const int MAX_MEM = 7e8;
int mpos = 0;
char mem[MAX_MEM];
inline void *operator new(size_t n) {
    assert((mpos += n) <= MAX_MEM);
    return (void *)(mem + mpos - n);
}
void operator delete(void *) noexcept {}          // must have!
void operator delete(void *, size_t) noexcept {}  // must have!

constexpr int maxn = 1e5 + 5, lg = 20;

vector<int> g1[maxn];

vector<int> g[maxn];

int tin[maxn], tout[maxn];

int t = 0;

int d[maxn];

// int used_arr[maxn];

int tin1[maxn];

void dfs1(int v, int pr) {
    tin1[v] = t++;
    for (auto u : g1[v]) {
        if (u != pr) {
            dfs1(u, v);
        }
    }
}

int pos[maxn];

vector<int> ord;

void dfs(int v, int pr) {
    tin[v] = t++;
    pos[v] = ord.size();
    ord.push_back(d[v]);
    for (auto u : g[v]) {
        if (u != pr) {
            d[u] = d[v] + 1;
            dfs(u, v);
            ord.push_back(d[v]);
        }
    }
    tout[v] = t;
}

int mn[lg][maxn * 2];

int pw[lg];

int vl[maxn * 2];

void build(int n) {
    dfs1(0, 0);
    for (int i = 0; i < n; ++i) {
        for (auto j : g1[i]) {
            g[tin1[i]].push_back(tin1[j]);
        }
    }
    t = 0;
    dfs(0, 0);
    for (int i = 0; i < (int)ord.size(); ++i) {
        mn[0][i] = ord[i];
    }
    for (int i = 0; i < lg; ++i) {
        pw[i] = (1 << i);
    }
    for (int i = 2; i < maxn * 2; ++i) {
        vl[i] = vl[i / 2] + 1;
    }
    for (int i = 1; i < lg; ++i) {
        for (int l = 0; l + pw[i] <= (int)ord.size(); ++l) {
            int r = l + pw[i];
            mn[i][l] = min(mn[i - 1][l], mn[i - 1][r - pw[i - 1]]);
        }
    }
}

int lca(int a, int b) {
    // return min(a, b);
    a = pos[a], b = pos[b];
    if (a > b) {
        swap(a, b);
    }
    b++;
    int len = b - a;
    int l = vl[len];
    return min(mn[l][a], mn[l][b - pw[l]]);
}

constexpr int sq = 317;

vector<pair<int, int>> qs[sq];

constexpr int R = 1 << 17;

int sum[R * 2];

void change(int pos, int val) {
    pos += R;
    sum[pos] = val;
    for (pos /= 2; pos > 0; pos /= 2) {
        sum[pos] = sum[pos * 2] + sum[pos * 2 + 1];
    }
}

int get_l(int pos) {
    pos += R;
    int prv = pos;
    pos /= 2;
    while (sum[pos * 2] == 0 || prv == pos * 2) {
        prv = pos;
        pos /= 2;
    }
    pos = pos * 2;
    while (pos < R) {
        if (sum[pos * 2 + 1]) {
            pos = pos * 2 + 1;
        } else {
            pos = pos * 2;
        }
    }
    return pos - R;
}

int get_r(int pos) {
    pos += R;
    int prv = pos;
    pos /= 2;
    while (sum[pos * 2 + 1] == 0 || prv == pos * 2 + 1) {
        prv = pos;
        pos /= 2;
    }
    pos = pos * 2 + 1;
    while (pos < R) {
        if (sum[pos * 2]) {
            pos = pos * 2;
        } else {
            pos = pos * 2 + 1;
        }
    }
    return pos - R;
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g1[a].push_back(b);
        g1[b].push_back(a);
    }
    build(n);
    vector<int> c(m);
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
        c[i]--;
        c[i] = tin1[c[i]];
    }
    vector<int> l(q), r(q), ans(q);
    for (int i = 0; i < q; ++i) {
        cin >> l[i] >> r[i];
        l[i]--;
        qs[l[i] / sq].emplace_back(r[i], i);
    }
    for (int st = 0; st < sq; ++st) {
        sort(qs[st].begin(), qs[st].end());
        int ans_nw = 0, root_d = -1, mn = -1, mx = -1;
        int pos = (st + 1) * sq;
        for (auto [rr, ind] : qs[st]) {
            while (pos < rr) {
                if (root_d == -1) {
                    ans_nw = 1;
                    root_d = d[c[pos]];
                    mn = mx = c[pos];
                    change(c[pos], 1);
                    pos++;
                } else {
                    if (sum[c[pos] + R]) {
                        pos++;
                        continue;
                    }
                    if (mx < c[pos]) {
                        int dv = lca(c[pos], mx);
                        ans_nw += d[c[pos]] - dv;
                        if (dv < root_d) {
                            ans_nw += root_d - dv;
                            root_d = dv;
                        }
                        mx = c[pos];
                    } else if (c[pos] < mn) {
                        int dv = lca(c[pos], mn);
                        ans_nw += d[c[pos]] - dv;
                        if (dv < root_d) {
                            ans_nw += root_d - dv;
                            root_d = dv;
                        }
                        mn = c[pos];
                    } else {
                        int v1 = get_r(c[pos]), v2 = get_l(c[pos]);
                        v1 = lca(v1, c[pos]);
                        v2 = lca(v2, c[pos]);
                        ans_nw += d[c[pos]] - max(v1, v2);
                    }
                    change(c[pos], 1);
                    pos++;
                }
            }
            vector<int> add;
            int ans_nw_start = ans_nw, root_d_start = root_d, mn_start = mn, mx_start = mx;
            if (root_d == -1) {
                ans_nw = 1;
                root_d = d[c[l[ind]]];
                mn = mx = c[l[ind]];
                change(c[l[ind]], 1);
                add.push_back(c[l[ind]]);
            }
            for (int i = l[ind]; i < r[ind] && i < (st + 1) * sq; ++i) {
                if (sum[c[i] + R]) {
                    continue;
                }
                add.push_back(c[i]);
                if (mx < c[i]) {
                    int dv = lca(c[i], mx);
                    ans_nw += d[c[i]] - dv;
                    if (dv < root_d) {
                        ans_nw += root_d - dv;
                        root_d = dv;
                    }
                    mx = c[i];
                } else if (c[i] < mn) {
                    int dv = lca(c[i], mn);
                    ans_nw += d[c[i]] - dv;
                    if (dv < root_d) {
                        ans_nw += root_d - dv;
                        root_d = dv;
                    }
                    mn = c[i];
                } else {
                    int v1 = get_r(c[i]), v2 = get_l(c[i]);
                    v1 = lca(c[i], v1);
                    v2 = lca(c[i], v2);
                    ans_nw += d[c[i]] - max(v1, v2);
                }
                change(c[i], 1);
            }
            ans[ind] = ans_nw;
            for (auto vl : add) {
                change(vl, 0);
            }
            ans_nw = ans_nw_start;
            root_d = root_d_start;
            mn = mn_start;
            mx = mx_start;
        }
        for (int i = 0; i < n; ++i) {
            if (sum[i + R]) {
                change(i, 0);
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    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