Submission #763576

#	Time	Username	Problem	Language	Result	Execution time	Memory
763576		CDuong	Tourism (JOI23_tourism)	C++17	28 / 100	5098 ms	50224 KiB

tourism

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")


#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
using namespace std;

const int mxN = 1e5 + 5;
const int mod = 1e9 + 7;
const int block = 350;
const ll oo = 1e18;

struct query {
    int l, r, idx;
    query() {};
    query(int l, int r, int idx) : l(l), r(r), idx(idx) {}
    bool operator < (const query &o) const {
        int cur_blk = l / block;
        if(cur_blk != o.l / block) return l < o.l;
        return (cur_blk & 1 ? r > o.r : r < o.r);
    }
};

vi G[mxN];
set<pii> cur_tree;
pii euler_tour[18][2 * mxN];
int n, m, q, c[mxN], res, ans[mxN], cnt[mxN];
int tin[mxN], tout[mxN], dep[mxN], frst_ap[mxN], euler_cnt, timer;
vector<query> queries;

void dfs(int v, int p) {
    tin[v] = ++timer;
    dep[v] = dep[p] + 1;
    frst_ap[v] = ++euler_cnt;
    euler_tour[0][euler_cnt] = {dep[v], v};

    for(int u : G[v]) {
        if(u == p) continue;
        dfs(u, v);
        euler_tour[0][++euler_cnt] = {dep[v], v};
    }

    tout[v] = timer;
}

void build_sparse() {
    for(int i = 1; (1 << i) <= euler_cnt; ++i) {
        for(int j = 1; j + (1 << i) - 1 <= euler_cnt; ++j) {
            euler_tour[i][j] = min(euler_tour[i - 1][j], euler_tour[i - 1][j + (1 << (i - 1))]);
        }
    }
}

int lca(int u, int v) {
    int l = frst_ap[u], r = frst_ap[v];
    if(l > r) swap(l, r);
    int len = r - l + 1;
    int lg_len = 31 - __builtin_clz(len);
    return min(euler_tour[lg_len][l], euler_tour[lg_len][r - (1 << lg_len) + 1]).ss;
}

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

int ll_nxt[mxN], ll_pre[mxN];

void add_linked_list(int idx, int nxt) {
    int pre = ll_pre[nxt];
    res += dis(pre, idx);
    res += dis(nxt, idx);
    res -= dis(pre, nxt);
    ll_nxt[pre] = ll_pre[nxt] = idx;
    ll_nxt[idx] = nxt, ll_pre[idx] = pre;
}

void del_linked_list(int idx) {
    int pre = ll_pre[idx], nxt = ll_nxt[idx];
    res -= dis(pre, idx);
    res -= dis(nxt, idx);
    res += dis(pre, nxt);
    ll_nxt[pre] = nxt, ll_pre[nxt] = pre;
}

void add(int idx) {
    ++cnt[c[idx]];
    if(cnt[c[idx]] > 1) return;
    int val = tin[c[idx]];
    if(cur_tree.empty()) {
        cur_tree.insert({val, c[idx]});
        ll_nxt[c[idx]] = ll_pre[c[idx]] = c[idx];
        return;
    }
    auto it = cur_tree.lower_bound({val, 0});
    int nxt = (it == cur_tree.end() ? (*cur_tree.begin()).ss : (*it).ss);
    add_linked_list(c[idx], nxt);
    cur_tree.insert({val, c[idx]});
}

void del(int idx) {
    --cnt[c[idx]];
    if(cnt[c[idx]]) return;
    int val = tin[c[idx]];
    cur_tree.erase({val, c[idx]});
    if(cur_tree.empty()) return;
    del_linked_list(c[idx]);
}

void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);
    build_sparse();
    for(int i = 1; i <= m; ++i) {
        cin >> c[i];
    }
    for(int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        queries.emplace_back(l, r, i);
    }
    sort(all(queries));
    int cur_l = 1, cur_r = 0;
    for(auto &[l, r, idx] : queries) {
        while(cur_l > l) add(--cur_l);
        while(cur_r < r) add(++cur_r);

        while(cur_l < l) del(cur_l++);
        while(cur_r > r) del(cur_r--);

        // cout << res << endl;
        // for(auto tmp : cur_tree) {
        //     cout << tmp.ff << " " << tmp.ss << endl;
        // }
        // cout << endl;

        ans[idx] = res / 2 + 1;
    }
    for(int i = 1; i <= q; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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