Submission #1119289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119289		MrAndria	Tourism (JOI23_tourism)	C++14	28 / 100	5070 ms	33764 KiB

tourism

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back

const int MAXN = 200005;
int n, m, q, k, u, v, lg;
int tin[MAXN], tout[MAXN], val[MAXN], dst[MAXN], timer = 0;
int up[MAXN][25], a[MAXN], num[MAXN], ans[MAXN];
pair<pair<int, int>, int> query[MAXN];
vector<int> adj[MAXN];
set<int> active;
int sz = 0;

void dfs(int x, int p, int depth) {
    tin[x] = timer++;
    val[tin[x]] = x;
    dst[x] = depth;
    up[x][0] = p;
    for (int i = 1; i <= lg; ++i)
        up[x][i] = up[up[x][i - 1]][i - 1];
    for (int neighbor : adj[x]) {
        if (neighbor != p) {
            dfs(neighbor, x, depth + 1);
        }
    }
    tout[x] = timer++;
}

inline bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

inline int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = lg; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}
inline set <int> :: iterator pre(set <int> :: iterator it){
    it--;
    return it;
}
inline set <int> :: iterator nex(set <int> :: iterator it){
    it++;
    return it;
}
inline int dist(int x, int y) {
    return dst[x] + dst[y] - 2 * dst[lca(x, y)];
}

inline void add(int x) {
    num[x]++;
    if (num[x] > 1) return;

    if (active.empty()) {
        active.insert(tin[x]);
        return;
    }

    auto it = active.insert(tin[x]).first;
    auto prev = it == active.begin() ? --active.end() : pre(it);
    auto next = nex(it) == active.end() ? active.begin() : nex(it);

    sz += dist(val[*prev], val[*it]) + dist(val[*it], val[*next]) - dist(val[*prev], val[*next]);
}

inline void remove(int x) {
    num[x]--;
    if (num[x] > 0) return;

    auto it = active.find(tin[x]);
    auto prev = it == active.begin() ? --active.end() : pre(it);
    auto next = nex(it) == active.end() ? active.begin() : nex(it);

    sz -= dist(val[*prev], val[*it]) + dist(val[*it], val[*next]) - dist(val[*prev], val[*next]);
    active.erase(it);
}

inline bool compare_queries(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    int block_a = a.ff.ff / k, block_b = b.ff.ff / k;
    if (block_a != block_b) return block_a < block_b;
    return block_a % 2 ? a.ff.ss > b.ff.ss : a.ff.ss < b.ff.ss;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;

    lg = ceil(log2(n));
    k = ceil(sqrt(m));

    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= q; i++) {
        cin >> query[i].ff.ff >> query[i].ff.ss;
        query[i].ss = i;
    }

    dfs(1, 1, 0);
    sort(query + 1, query + q + 1, compare_queries);

    int tl = 1, tr = 1;
    add(a[tl]);

    for (int i = 1; i <= q; i++) {
        int l = query[i].ff.ff, r = query[i].ff.ss;
        while (tr < r) add(a[++tr]);
        while (tl > l) add(a[--tl]);
        while (tr > r) remove(a[tr--]);
        while (tl < l) remove(a[tl++]);

        ans[query[i].ss] = (sz / 2) + 1;
    }

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << " ";
    }
}

Compilation message (stderr)

tourism.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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