Submission #1303096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303096		tonytung_123	Tourism (JOI23_tourism)	C++20	28 / 100	5097 ms	46196 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

#define task "Tourism"
using pii = pair<int,int>;
using ll = long long;

struct Query {
    int l, r, i;
    long long ord;
};

const int N = 100000 + 5;
const int LG = 20;          // enough for 2*N <= 2e5
vector<int> ad[N];
int n, m, q;
int tin[N], depthArr[N], c[200000+5], cnt[N], ans[N];
pair<int,int> rmq[LG+1][2*N];
int timer = 0;
set<pii> nodes;
long long tot = 0;
Query que[200000+5];
int LOG2[2*N];

inline long long hilbertOrder(int x, int y, int pow=21, int rotate=0) {
    if (pow == 0) return 0;
    int hpow = 1 << (pow-1);
    int seg = (x < hpow) ? ( (y < hpow) ? 0 : 3 ) : ( (y < hpow) ? 1 : 2 );
    const int rotateDelta[4] = {3,0,0,1};
    int nx = x & (hpow-1), ny = y & (hpow-1);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    long long subSquareSize = 1LL << (2*pow - 2);
    long long ans = seg * subSquareSize + hilbertOrder(nx, ny, pow-1, nrot);
    if (seg == 1) { swap(nx, ny); }
    else if (seg == 2) { nx = hpow-1 - nx; ny = hpow-1 - ny; }
    else if (seg == 3) { swap(nx, ny); nx = hpow-1 - nx; ny = hpow-1 - ny; }
    return ans;
}

void dfs(int u, int p) {
    tin[u] = ++timer;
    rmq[0][timer] = { depthArr[u], u };
    for (int v : ad[u]) {
        if (v == p) continue;
        depthArr[v] = depthArr[u] + 1;
        dfs(v, u);
        // after returning to u, push u again (standard euler tour for RMQ LCA)
        rmq[0][++timer] = { depthArr[u], u };
    }
}

inline int lca(int u, int v) {
    int l = tin[u], r = tin[v];
    if (l > r) swap(l, r);
    int k = LOG2[r - l + 1];
    auto a = rmq[k][l];
    auto b = rmq[k][r - (1<<k) + 1];
    return (a.first <= b.first ? a.second : b.second);
}

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

pii find_neighbors(int u) {
    auto it = nodes.lower_bound({tin[u], -1});
    pii res;
    if (it == nodes.end()) {
        --it;
        res.first = it->second;
        res.second = nodes.begin()->second;
    } else if (it == nodes.begin()) {
        res.first = it->second;
        res.second = nodes.rbegin()->second;
    } else {
        res.first = it->second;
        --it;
        res.second = it->second;
    }
    return res;
}

inline void addNode(int u) {
    if (++cnt[u] != 1) return;
    if (nodes.empty()) {
        nodes.insert({tin[u], u});
        return;
    }
    if (nodes.size() == 1) {
        int v = nodes.begin()->second;
        tot += 2LL * dist(u, v);
        nodes.insert({tin[u], u});
        return;
    }
    auto pr = find_neighbors(u);
    tot += dist(pr.first, u) + dist(u, pr.second) - dist(pr.first, pr.second);
    nodes.insert({tin[u], u});
}

inline void delNode(int u) {
    if (--cnt[u] != 0) return;
    if (nodes.size() == 1) {
        nodes.erase(nodes.find({tin[u], u}));
        return;
    }
    if (nodes.size() == 2) {
        nodes.erase(nodes.find({tin[u], u}));
        tot = 0;
        return;
    }
    // remove then fix tot using neighbor pair
    auto it = nodes.find({tin[u], u});
    // get neighbors BEFORE erasing: prev and next in cyclic order
    auto itNext = next(it);
    if (itNext == nodes.end()) itNext = nodes.begin();
    auto itPrev = (it == nodes.begin() ? prev(nodes.end()) : prev(it));
    int v1 = itPrev->second;
    int v2 = itNext->second;
    tot -= dist(v1, u) + dist(u, v2) - dist(v1, v2);
    nodes.erase(it);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

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

    timer = 0;
    depthArr[1] = 0;
    dfs(1, 0);
    int M = timer;                     // length of euler tour

    // precompute logs
    LOG2[1] = 0;
    for (int i = 2; i <= M; ++i) LOG2[i] = LOG2[i/2] + 1;

    // build sparse table only up to M
    for (int j = 1; (1<<j) <= M; ++j) {
        int len = (1<<j);
        for (int i = 1; i + len - 1 <= M; ++i) {
            auto &a = rmq[j-1][i];
            auto &b = rmq[j-1][i + (1<<(j-1))];
            rmq[j][i] = (a.first <= b.first ? a : b);
        }
    }

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

    for (int i = 1; i <= q; ++i) {
        cin >> que[i].l >> que[i].r;
        que[i].i = i;
        que[i].ord = hilbertOrder(que[i].l, que[i].r, 21);
    }

    sort(que+1, que+q+1, [](const Query &a, const Query &b){
        return a.ord < b.ord;
    });

    int L = 1, R = 0;
    // clean global state
    nodes.clear();
    fill(cnt, cnt+n+1, 0);
    tot = 0;

    for (int idx = 1; idx <= q; ++idx) {
        int ql = que[idx].l, qr = que[idx].r;
        while (L > ql) addNode(c[--L]);
        while (R < qr) addNode(c[++R]);
        while (L < ql) delNode(c[L++]);
        while (R > qr) delNode(c[R--]);
        ans[que[idx].i] = (int)(tot/2 + 1);
    }

    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(task".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