Submission #1189338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189338		anmattroi	Tourism (JOI23_tourism)	C++20	42 / 100	4767 ms	45356 KiB

tourism

#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 100005
using namespace std;
using ii = pair<int, int>;

const int B = 320;

inline constexpr int csk(const int &x) {return (x-1)/B+1;}

int n, m, q, d[maxn], c[maxn], id = 0, firstOrder[maxn], euler[maxn+maxn];
vector<int> adj[maxn];

ii f[18][maxn+maxn];

void myAssert(int condition) {
    if (!condition)
        while (1) {}
}

void pfs(int u, int dad) {
    f[0][++id] = ii{d[u], u};
    firstOrder[u] = id;
    euler[id] = u;

    for (int v : adj[u])
    if (v != dad) {
        d[v] = d[u] + 1;
        pfs(v, u);
        f[0][++id] = ii{d[u], u};
    }
}

int lca(int u, int v) {
    u = firstOrder[u]; v = firstOrder[v];
    if (u > v) swap(u, v);
    int k = __lg(v-u+1);
    return min(f[k][u], f[k][v-(1<<k)+1]).se;
}

int dis(int u, int v) {
    return d[u] + d[v] - 2 * d[lca(u, v)];
}

int cnt[maxn], ans = 0;

multiset<int> s;

void add(int x) {
    ++cnt[x];
    if (cnt[x] > 1) return;
    x = firstOrder[x];
    auto it = s.insert(x);
    if (next(it) != s.end() && it != s.begin()) {
        int a = *prev(it), b = *next(it);
        ans += dis(euler[x], euler[b]);
        ans += dis(euler[x], euler[a]);
        ans -= dis(euler[a], euler[b]);
        return;
    }
    if (next(it) != s.end()) {
        int y = *next(it);
        ans += dis(euler[x], euler[y]);
        return;
    }
    if (it != s.begin()) {
        int y = *prev(it);
        ans += dis(euler[x], euler[y]);
        return;
    }
}

void del(int x) {
    --cnt[x];
    if (cnt[x] > 0) return;
    x = firstOrder[x];
    auto it = s.find(x);
    if (next(it) != s.end() && it != s.begin()) {
        int a = *prev(it), b = *next(it);
        ans -= dis(euler[x], euler[b]);
        ans -= dis(euler[x], euler[a]);
        ans += dis(euler[a], euler[b]);
        s.erase(it);
        return;
    }
    if (next(it) != s.end()) {
        int y = *next(it);
        ans -= dis(euler[x], euler[y]);
        s.erase(it);
        return;
    }
    if (it != s.begin()) {
        int y = *prev(it);
        ans -= dis(euler[x], euler[y]);
        s.erase(it);
        return;
    }
}

struct query {
    int l, r, idx;
    query() {}
    query(int _l, int _r, int _idx) : l(_l), r(_r), idx(_idx) {}

    bool operator < (const query &other) const {
        int u = csk(l), v = csk(other.l);
        if (u != v) return u < v;
        return ((u&1)^(r<other.r));
    }
} queries[maxn];

int kq[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    pfs(1, 0);
    for (int i = 1; i <= m; i++) cin >> c[i];
    for (int i = 1; (1<<i) <= id; i++) for (int j = 1; j + (1<<i) - 1 <= id; j++) f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);

    for (int i = 1; i <= q; i++) {cin >> queries[i].l >> queries[i].r; queries[i].idx = i;}

    sort(queries + 1, queries + q + 1);

    int L = 1, R = 0;

    for (int o = 1; o <= q; o++) {
        auto [l, r, idx] = queries[o];
        while (R < r) add(c[++R]);
        while (L > l) add(c[--L]);
        while (R > r) del(c[R--]);
        while (L < l) del(c[L++]);
        myAssert(!s.empty());
        kq[idx] = ans + dis(euler[*s.begin()], euler[*s.rbegin()]);
    }
    for (int i = 1; i <= q; i++) cout << kq[i]/2+1 << "\n";
}

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