oj.uz

Submission #763603

# Submission time Handle Problem Language Result Execution time Memory
763603 2023-06-22T13:48:02 Z CDuong Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 47816 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 = 400;
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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 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 2772 KB Output is correct
7 Correct 3 ms 2772 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 2772 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 2772 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 2856 KB Output is correct
19 Correct 4 ms 2860 KB Output is correct
20 Correct 4 ms 2772 KB Output is correct
21 Correct 4 ms 2772 KB Output is correct
22 Correct 4 ms 2852 KB Output is correct
23 Correct 4 ms 2772 KB Output is correct
24 Correct 4 ms 2772 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 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 2772 KB Output is correct
7 Correct 3 ms 2772 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 2772 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 2772 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 2856 KB Output is correct
19 Correct 4 ms 2860 KB Output is correct
20 Correct 4 ms 2772 KB Output is correct
21 Correct 4 ms 2772 KB Output is correct
22 Correct 4 ms 2852 KB Output is correct
23 Correct 4 ms 2772 KB Output is correct
24 Correct 4 ms 2772 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 24 ms 3200 KB Output is correct
31 Correct 33 ms 3188 KB Output is correct
32 Correct 35 ms 3352 KB Output is correct
33 Correct 36 ms 3352 KB Output is correct
34 Correct 37 ms 3348 KB Output is correct
35 Correct 4 ms 3284 KB Output is correct
36 Correct 4 ms 3284 KB Output is correct
37 Correct 4 ms 3284 KB Output is correct
38 Correct 34 ms 3460 KB Output is correct
39 Correct 34 ms 3460 KB Output is correct
40 Correct 36 ms 3476 KB Output is correct
41 Correct 4 ms 3412 KB Output is correct
42 Correct 4 ms 3412 KB Output is correct
43 Correct 4 ms 3412 KB Output is correct
44 Correct 36 ms 3392 KB Output is correct
45 Correct 35 ms 3384 KB Output is correct
46 Correct 35 ms 3400 KB Output is correct
47 Correct 4 ms 3412 KB Output is correct
48 Correct 4 ms 3284 KB Output is correct
49 Correct 6 ms 3412 KB Output is correct
50 Correct 34 ms 3336 KB Output is correct
51 Correct 31 ms 3284 KB Output is correct
52 Correct 37 ms 3284 KB Output is correct
53 Correct 33 ms 3364 KB Output is correct
54 Correct 32 ms 3360 KB Output is correct
55 Correct 33 ms 3284 KB Output is correct
56 Correct 3 ms 2772 KB Output is correct
57 Correct 3 ms 3284 KB Output is correct
58 Correct 4 ms 3284 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 4574 ms 28280 KB Output is correct
5 Correct 3542 ms 38420 KB Output is correct
6 Correct 4664 ms 43552 KB Output is correct
7 Execution timed out 5068 ms 47816 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 78 ms 20072 KB Output is correct
3 Correct 119 ms 21724 KB Output is correct
4 Correct 96 ms 24368 KB Output is correct
5 Correct 95 ms 38504 KB Output is correct
6 Correct 118 ms 37804 KB Output is correct
7 Correct 159 ms 36352 KB Output is correct
8 Correct 127 ms 35904 KB Output is correct
9 Correct 124 ms 35696 KB Output is correct
10 Correct 130 ms 35532 KB Output is correct
11 Correct 184 ms 35532 KB Output is correct
12 Correct 153 ms 35592 KB Output is correct
13 Correct 153 ms 35860 KB Output is correct
14 Correct 168 ms 36204 KB Output is correct
15 Correct 159 ms 37400 KB Output is correct
16 Correct 148 ms 37396 KB Output is correct
17 Correct 150 ms 37424 KB Output is correct
18 Correct 153 ms 37468 KB Output is correct
19 Correct 115 ms 38532 KB Output is correct
20 Correct 99 ms 38540 KB Output is correct
21 Correct 118 ms 37068 KB Output is correct
22 Correct 136 ms 36488 KB Output is correct
23 Correct 119 ms 36052 KB Output is correct
24 Correct 121 ms 35812 KB Output is correct
25 Correct 131 ms 35588 KB Output is correct
26 Correct 109 ms 35716 KB Output is correct
27 Correct 145 ms 35756 KB Output is correct
28 Correct 147 ms 35640 KB Output is correct
29 Correct 180 ms 35632 KB Output is correct
30 Correct 148 ms 35832 KB Output is correct
31 Correct 151 ms 35956 KB Output is correct
32 Correct 151 ms 36068 KB Output is correct
33 Correct 147 ms 36564 KB Output is correct
34 Correct 169 ms 37596 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 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Execution timed out 5043 ms 24080 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 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 2772 KB Output is correct
7 Correct 3 ms 2772 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 2772 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 2772 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 2856 KB Output is correct
19 Correct 4 ms 2860 KB Output is correct
20 Correct 4 ms 2772 KB Output is correct
21 Correct 4 ms 2772 KB Output is correct
22 Correct 4 ms 2852 KB Output is correct
23 Correct 4 ms 2772 KB Output is correct
24 Correct 4 ms 2772 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 24 ms 3200 KB Output is correct
31 Correct 33 ms 3188 KB Output is correct
32 Correct 35 ms 3352 KB Output is correct
33 Correct 36 ms 3352 KB Output is correct
34 Correct 37 ms 3348 KB Output is correct
35 Correct 4 ms 3284 KB Output is correct
36 Correct 4 ms 3284 KB Output is correct
37 Correct 4 ms 3284 KB Output is correct
38 Correct 34 ms 3460 KB Output is correct
39 Correct 34 ms 3460 KB Output is correct
40 Correct 36 ms 3476 KB Output is correct
41 Correct 4 ms 3412 KB Output is correct
42 Correct 4 ms 3412 KB Output is correct
43 Correct 4 ms 3412 KB Output is correct
44 Correct 36 ms 3392 KB Output is correct
45 Correct 35 ms 3384 KB Output is correct
46 Correct 35 ms 3400 KB Output is correct
47 Correct 4 ms 3412 KB Output is correct
48 Correct 4 ms 3284 KB Output is correct
49 Correct 6 ms 3412 KB Output is correct
50 Correct 34 ms 3336 KB Output is correct
51 Correct 31 ms 3284 KB Output is correct
52 Correct 37 ms 3284 KB Output is correct
53 Correct 33 ms 3364 KB Output is correct
54 Correct 32 ms 3360 KB Output is correct
55 Correct 33 ms 3284 KB Output is correct
56 Correct 3 ms 2772 KB Output is correct
57 Correct 3 ms 3284 KB Output is correct
58 Correct 4 ms 3284 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 4574 ms 28280 KB Output is correct
63 Correct 3542 ms 38420 KB Output is correct
64 Correct 4664 ms 43552 KB Output is correct
65 Execution timed out 5068 ms 47816 KB Time limit exceeded
66 Halted 0 ms 0 KB -