Submission #1303086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303086		duckindog	Tourism (JOI23_tourism)	C++20	28 / 100	5093 ms	25764 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10,
            S = 300;
int n, m, q;
vector<int> ad[N];
int c[N];
struct Query {
    int l, r, idx;
    friend istream& operator >> (istream& is, Query& rhs) {
        return is >> rhs.l >> rhs.r;
    }
} query[N];

int depth[N];
int st[N], ed[N], node[N], num;
void dfs(int u, int p = -1) {
    st[u] = ++num; node[num] = u;

    for (const auto& v : ad[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        node[++num] = u;
    }

    ed[u] = num;
}
inline bool isAnc(int u, int v) { return st[u] <= st[v] && ed[v] <= ed[u]; }

int up[N][18];
void initST() {
    for (int i = 1; i <= num; ++i) up[i][0] = node[i];

    for (int j = 1; j <= 17; ++j) {
        for (int i = 1; i <= num - (1 << j) + 1; ++i) {
            int lt = up[i][j - 1], rt = up[i + (1 << (j - 1))][j - 1];
            up[i][j] = (st[lt] < st[rt] ? lt : rt);
        }
    }
}
inline int lca(int u, int v) {
    int l = min(st[u], st[v]), r = max(st[u], st[v]);
    int j = __lg(r - l + 1);

    int lt = up[l][j], rt = up[r - (1 << j) + 1][j];
    return st[lt] < st[rt] ? lt : rt;
}

inline int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }

int cnt[N];

int answer[N];

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

    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    if (fopen("tourism.inp", "r")) {
        freopen("tourism.inp", "r", stdin);
        freopen("tourism.out", "w", stdout);
    }

    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    for (int i = 1; i <= m; ++i) cin >> c[i];
    for (int i = 1; i <= q; ++i) cin >> query[i], query[i].idx = i;

    dfs(1);
    initST();

    int cur = 0;
    set<int> s;

    auto add = [&](int i) {
        int u = c[i];
        cnt[u] += 1;
        if (cnt[u] != 1) return;

        s.insert(st[u]);
        auto it = s.lower_bound(st[u]);
        if (it != s.begin() && it != prev(s.end())) {
            int l = node[*prev(it)], r = node[*next(it)];
            cur -= dist(l, r);
        }
        if (it != s.begin()) {
            int l = node[*prev(it)];
            cur += dist(l, u);
        }
        if (it != prev(s.end())) {
            int r = node[*next(it)];
            cur += dist(u, r);
        }
    };
    auto del = [&](int i) {
        int u = c[i];
        cnt[u] -= 1;
        if (cnt[u] != 0) return;

        auto it = s.lower_bound(st[u]);
        if (it != s.begin()) {
            int l = node[*prev(it)];
            cur -= dist(l, u);
        }
        if (it != prev(s.end())) {
            int r = node[*next(it)];
            cur -= dist(u, r);
        }
        if (it != s.begin() && it != prev(s.end())) {
            int l = node[*prev(it)], r = node[*next(it)];
            cur += dist(l, r);
        }
        s.erase(st[u]);
    };

    sort(query + 1, query + q + 1, [&](const auto& i, const auto& j) {
        return make_pair((i.l - 1) / S + 1, i.r) < make_pair((j.l - 1) / S + 1, j.r);
    });

    int lt = 1, rt = 0;
    for (int iQ = 1; iQ <= q; ++iQ) {
        const auto& l = query[iQ].l;
        const auto& r = query[iQ].r;
        const auto& idx = query[iQ].idx;

        while (rt < r) add(++rt);
        while (lt < l) del(lt++);
        while (rt > r) del(rt--);
        while (lt > l) add(--lt);

        int trueCur = cur + dist(node[*s.begin()], node[*s.rbegin()]);
        int spanningtree = trueCur / 2;

        answer[idx] = spanningtree + 1;
    }

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

Compilation message (stderr)

tourism.cpp: In function 'int32_t main()':
tourism.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen("tourism.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("tourism.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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