oj.uz

Submission #763596

# Submission time Handle Problem Language Result Execution time Memory
763596 2023-06-22T13:38:44 Z CDuong Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 50596 KB 
#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;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
// - insert(x)
// - find_by_order(k): return iterator to the k-th smallest element
// - order_of_key(x): the number of elements that are strictly smaller

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];
ordered_set cur_tree;
pii euler_tour[18][2 * mxN];
int n, m, q, c[mxN], res, ans[mxN], cnt[mxN], cur_tree_sz;
int tin[mxN], rev_tin[mxN], tout[mxN], dep[mxN], frst_ap[mxN], euler_cnt, timer;
vector<query> queries;

void dfs(int v, int p) {
    tin[v] = ++timer;
    rev_tin[timer] = v;
    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);
    // cout << pre << " " << idx << " " << res << endl;
    res += dis(nxt, idx);
    // cout << pre << " " << idx << " " << res << endl;
    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_sz == 0) {
        ++cur_tree_sz;
        cur_tree.insert(val);
        ll_nxt[c[idx]] = ll_pre[c[idx]] = c[idx];
        return;
    }
    int cur = cur_tree.order_of_key(val), nxt;
    if(cur == cur_tree_sz) nxt = (*(cur_tree.find_by_order(0)));
    else nxt = (*(cur_tree.find_by_order(cur)));
    // cout << c[idx] << " " << nxt << endl;
    add_linked_list(c[idx], rev_tin[nxt]);
    cur_tree.insert(val);
    ++cur_tree_sz;
}

void del(int idx) {
    --cnt[c[idx]];
    if(cnt[c[idx]]) return;
    int val = tin[c[idx]];
    cur_tree.erase(val);
    --cur_tree_sz;
    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 >> 1) + 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2720 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2748 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 4 ms 2772 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 4 ms 2816 KB Output is correct
20 Correct 5 ms 2820 KB Output is correct
21 Correct 4 ms 2860 KB Output is correct
22 Correct 4 ms 2780 KB Output is correct
23 Correct 4 ms 2772 KB Output is correct
24 Correct 4 ms 2828 KB Output is correct
25 Correct 4 ms 2772 KB Output is correct
26 Correct 4 ms 2772 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 2 ms 2772 KB Output is correct
29 Correct 2 ms 2772 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2720 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2748 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 4 ms 2772 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 4 ms 2816 KB Output is correct
20 Correct 5 ms 2820 KB Output is correct
21 Correct 4 ms 2860 KB Output is correct
22 Correct 4 ms 2780 KB Output is correct
23 Correct 4 ms 2772 KB Output is correct
24 Correct 4 ms 2828 KB Output is correct
25 Correct 4 ms 2772 KB Output is correct
26 Correct 4 ms 2772 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 2 ms 2772 KB Output is correct
29 Correct 2 ms 2772 KB Output is correct
30 Correct 25 ms 3272 KB Output is correct
31 Correct 30 ms 3236 KB Output is correct
32 Correct 32 ms 3392 KB Output is correct
33 Correct 31 ms 3336 KB Output is correct
34 Correct 30 ms 3396 KB Output is correct
35 Correct 4 ms 3412 KB Output is correct
36 Correct 4 ms 3336 KB Output is correct
37 Correct 4 ms 3412 KB Output is correct
38 Correct 31 ms 3400 KB Output is correct
39 Correct 31 ms 3412 KB Output is correct
40 Correct 30 ms 3524 KB Output is correct
41 Correct 5 ms 3460 KB Output is correct
42 Correct 6 ms 3460 KB Output is correct
43 Correct 5 ms 3412 KB Output is correct
44 Correct 39 ms 3440 KB Output is correct
45 Correct 31 ms 3400 KB Output is correct
46 Correct 31 ms 3412 KB Output is correct
47 Correct 4 ms 3412 KB Output is correct
48 Correct 4 ms 3412 KB Output is correct
49 Correct 5 ms 3452 KB Output is correct
50 Correct 30 ms 3332 KB Output is correct
51 Correct 28 ms 3388 KB Output is correct
52 Correct 29 ms 3404 KB Output is correct
53 Correct 30 ms 3412 KB Output is correct
54 Correct 31 ms 3400 KB Output is correct
55 Correct 29 ms 3284 KB Output is correct
56 Correct 3 ms 2700 KB Output is correct
57 Correct 3 ms 3340 KB Output is correct
58 Correct 5 ms 3332 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 4597 ms 30276 KB Output is correct
5 Correct 3424 ms 40420 KB Output is correct
6 Correct 4888 ms 45700 KB Output is correct
7 Execution timed out 5055 ms 50596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 83 ms 21020 KB Output is correct
3 Correct 113 ms 22912 KB Output is correct
4 Correct 96 ms 25580 KB Output is correct
5 Correct 99 ms 40272 KB Output is correct
6 Correct 129 ms 39724 KB Output is correct
7 Correct 136 ms 38144 KB Output is correct
8 Correct 130 ms 37632 KB Output is correct
9 Correct 123 ms 37416 KB Output is correct
10 Correct 162 ms 37376 KB Output is correct
11 Correct 152 ms 37324 KB Output is correct
12 Correct 156 ms 37448 KB Output is correct
13 Correct 161 ms 37716 KB Output is correct
14 Correct 167 ms 38328 KB Output is correct
15 Correct 155 ms 40308 KB Output is correct
16 Correct 153 ms 39272 KB Output is correct
17 Correct 152 ms 39304 KB Output is correct
18 Correct 148 ms 39264 KB Output is correct
19 Correct 103 ms 40236 KB Output is correct
20 Correct 105 ms 40292 KB Output is correct
21 Correct 118 ms 38880 KB Output is correct
22 Correct 121 ms 38092 KB Output is correct
23 Correct 122 ms 37776 KB Output is correct
24 Correct 116 ms 37452 KB Output is correct
25 Correct 110 ms 37412 KB Output is correct
26 Correct 121 ms 37452 KB Output is correct
27 Correct 132 ms 37336 KB Output is correct
28 Correct 140 ms 37380 KB Output is correct
29 Correct 182 ms 37428 KB Output is correct
30 Correct 149 ms 37616 KB Output is correct
31 Correct 153 ms 37808 KB Output is correct
32 Correct 166 ms 38128 KB Output is correct
33 Correct 156 ms 38912 KB Output is correct
34 Correct 143 ms 40444 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Execution timed out 5041 ms 26268 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2684 KB Output is correct
2 Correct 2 ms 2720 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2748 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2816 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 4 ms 2772 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 4 ms 2816 KB Output is correct
20 Correct 5 ms 2820 KB Output is correct
21 Correct 4 ms 2860 KB Output is correct
22 Correct 4 ms 2780 KB Output is correct
23 Correct 4 ms 2772 KB Output is correct
24 Correct 4 ms 2828 KB Output is correct
25 Correct 4 ms 2772 KB Output is correct
26 Correct 4 ms 2772 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 2 ms 2772 KB Output is correct
29 Correct 2 ms 2772 KB Output is correct
30 Correct 25 ms 3272 KB Output is correct
31 Correct 30 ms 3236 KB Output is correct
32 Correct 32 ms 3392 KB Output is correct
33 Correct 31 ms 3336 KB Output is correct
34 Correct 30 ms 3396 KB Output is correct
35 Correct 4 ms 3412 KB Output is correct
36 Correct 4 ms 3336 KB Output is correct
37 Correct 4 ms 3412 KB Output is correct
38 Correct 31 ms 3400 KB Output is correct
39 Correct 31 ms 3412 KB Output is correct
40 Correct 30 ms 3524 KB Output is correct
41 Correct 5 ms 3460 KB Output is correct
42 Correct 6 ms 3460 KB Output is correct
43 Correct 5 ms 3412 KB Output is correct
44 Correct 39 ms 3440 KB Output is correct
45 Correct 31 ms 3400 KB Output is correct
46 Correct 31 ms 3412 KB Output is correct
47 Correct 4 ms 3412 KB Output is correct
48 Correct 4 ms 3412 KB Output is correct
49 Correct 5 ms 3452 KB Output is correct
50 Correct 30 ms 3332 KB Output is correct
51 Correct 28 ms 3388 KB Output is correct
52 Correct 29 ms 3404 KB Output is correct
53 Correct 30 ms 3412 KB Output is correct
54 Correct 31 ms 3400 KB Output is correct
55 Correct 29 ms 3284 KB Output is correct
56 Correct 3 ms 2700 KB Output is correct
57 Correct 3 ms 3340 KB Output is correct
58 Correct 5 ms 3332 KB Output is correct
59 Correct 2 ms 2644 KB Output is correct
60 Correct 2 ms 2644 KB Output is correct
61 Correct 3 ms 2772 KB Output is correct
62 Correct 4597 ms 30276 KB Output is correct
63 Correct 3424 ms 40420 KB Output is correct
64 Correct 4888 ms 45700 KB Output is correct
65 Execution timed out 5055 ms 50596 KB Time limit exceeded
66 Halted 0 ms 0 KB -