oj.uz

Submission #916671

# Submission time Handle Problem Language Result Execution time Memory
916671 2024-01-26T09:06:03 Z thangdz2k7 Tourism (JOI23_tourism) C++17
100 / 100
 1010 ms 30420 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define iii pair <ii, int>
#define F first
#define S second
#define pb push_back

using namespace std;

const int N = 1e5 + 5;

int n, m, q;
int c[N], l[N], r[N];
vector <int> adj[N], query[N];

int bit[N];

void update(int u, int v){
    while (u <= m){
        bit[u] += v;
        u += (u & (-u));
    }
}

int get(int u){
    int ans = 0;
    while (u > 0){
        ans += bit[u];
        u -= (u & (-u));
    }

    return ans;
}

int par[N], heavy[N], depth[N];

int dfs(int u, int pa){
    int sz = 1;
    par[u] = pa;
    int maxsz = 0;
    depth[u] = depth[pa] + 1;

    for (int v : adj[u]){
        if (v == pa) continue;
        int cur = dfs(v, u);
        sz += cur;
        if (maxsz < cur){
            maxsz = cur;
            heavy[u] = v;

        }
    }

    return sz;
}

int pos[N], head[N], cu;
set <ii> s;

void decompose(int u, int h){
    head[u] = h;
    ++ cu;
    pos[u] = cu;
    s.insert(ii(cu, cu));

    if (heavy[u]){
        decompose(heavy[u], h);
    }

    for (int v : adj[u]){
        if (v != par[u] && v != heavy[u]) decompose(v, v);
    }
}

int cur[N];

void add(int l, int r, int val){
    while (true){
        ii z = *s.lower_bound(ii(l, -1));
        if (z.F > r) break;
        s.erase(z);
        if (z.S > r) {
            s.insert(ii(r + 1, z.S));
            int le = r - z.F + 1;
            update(cur[z.F] + 1, le);
            update(val + 1, -le);
            cur[r + 1] = cur[z.F];
        }
        else {
            int le = z.S - z.F + 1;
            update(cur[z.F] + 1, le);
            update(val + 1, -le);
        }
    }

    ii z = *(--s.lower_bound(ii(l, -1)));
    if (z.S > r){
        s.erase(z);
        s.insert(ii(z.F, l - 1));
        s.insert(ii(r + 1, z.S));
        int le = r - l + 1;
        update(cur[z.F] + 1, le);
        update(val + 1, -le);
    }

    else if (z.S >= l){
         s.erase(z);
         s.insert(ii(z.F, l - 1));
         int le = z.S - l + 1;
         update(cur[z.F] + 1, le);
         update(val + 1, -le);
    }

    s.insert(ii(l, r));
    cur[l] = val;
}

void upd(int u, int v, int val){
    for (; head[u] != head[v]; v = par[head[v]]){
        if (depth[head[u]] > depth[head[v]]) swap(u, v);
        add(pos[head[v]], pos[v], val);

    }

    if (depth[u] > depth[v]) swap(u, v);
    add(pos[u], pos[v], val);
}

int ans[N];

void solve(){
    cin >> n >> m >> q;
    for (int i = 1, u, v; i <= n - 1; ++ i){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    for (int i = 1; i <= m; ++ i) cin >> c[i];
    for (int i = 1, r; i <= q; ++ i){
        cin >> l[i] >> r;
        query[r].pb(i);
    }

    dfs(1, 0);
    decompose(1, 1);

    s.insert(ii(0, 0)), s.insert(ii(n + 1, n + 1));

    for (int i = 1; i <= m; ++ i){
        if (i > 1) upd(c[i], c[i - 1], i - 1);
        for (int k : query[i]){
            ans[k] = max(1, get(l[k]));
        }
    }

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct
18 Correct 2 ms 8708 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 3 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 3 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8536 KB Output is correct
26 Correct 2 ms 8620 KB Output is correct
27 Correct 2 ms 8540 KB Output is correct
28 Correct 2 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct
18 Correct 2 ms 8708 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 3 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 3 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8536 KB Output is correct
26 Correct 2 ms 8620 KB Output is correct
27 Correct 2 ms 8540 KB Output is correct
28 Correct 2 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct
30 Correct 6 ms 8796 KB Output is correct
31 Correct 7 ms 8796 KB Output is correct
32 Correct 8 ms 8796 KB Output is correct
33 Correct 8 ms 8992 KB Output is correct
34 Correct 8 ms 8796 KB Output is correct
35 Correct 7 ms 8792 KB Output is correct
36 Correct 9 ms 8796 KB Output is correct
37 Correct 7 ms 8796 KB Output is correct
38 Correct 4 ms 8796 KB Output is correct
39 Correct 5 ms 8796 KB Output is correct
40 Correct 4 ms 8796 KB Output is correct
41 Correct 6 ms 8796 KB Output is correct
42 Correct 5 ms 8796 KB Output is correct
43 Correct 4 ms 8796 KB Output is correct
44 Correct 7 ms 8796 KB Output is correct
45 Correct 6 ms 8792 KB Output is correct
46 Correct 6 ms 8796 KB Output is correct
47 Correct 5 ms 8796 KB Output is correct
48 Correct 5 ms 8796 KB Output is correct
49 Correct 5 ms 8796 KB Output is correct
50 Correct 5 ms 8896 KB Output is correct
51 Correct 6 ms 8696 KB Output is correct
52 Correct 5 ms 8796 KB Output is correct
53 Correct 5 ms 8792 KB Output is correct
54 Correct 5 ms 8796 KB Output is correct
55 Correct 5 ms 8796 KB Output is correct
56 Correct 3 ms 8540 KB Output is correct
57 Correct 3 ms 8796 KB Output is correct
58 Correct 7 ms 8796 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 101 ms 19768 KB Output is correct
5 Correct 90 ms 23072 KB Output is correct
6 Correct 106 ms 24916 KB Output is correct
7 Correct 138 ms 27488 KB Output is correct
8 Correct 141 ms 27476 KB Output is correct
9 Correct 143 ms 27440 KB Output is correct
10 Correct 136 ms 27316 KB Output is correct
11 Correct 140 ms 27476 KB Output is correct
12 Correct 139 ms 26196 KB Output is correct
13 Correct 133 ms 26268 KB Output is correct
14 Correct 138 ms 26260 KB Output is correct
15 Correct 53 ms 25288 KB Output is correct
16 Correct 145 ms 27160 KB Output is correct
17 Correct 39 ms 11348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8544 KB Output is correct
2 Correct 293 ms 13148 KB Output is correct
3 Correct 467 ms 13780 KB Output is correct
4 Correct 357 ms 14236 KB Output is correct
5 Correct 626 ms 16728 KB Output is correct
6 Correct 627 ms 16980 KB Output is correct
7 Correct 610 ms 16980 KB Output is correct
8 Correct 588 ms 16980 KB Output is correct
9 Correct 561 ms 16976 KB Output is correct
10 Correct 590 ms 16984 KB Output is correct
11 Correct 583 ms 17264 KB Output is correct
12 Correct 612 ms 17076 KB Output is correct
13 Correct 618 ms 17328 KB Output is correct
14 Correct 614 ms 18192 KB Output is correct
15 Correct 665 ms 20512 KB Output is correct
16 Correct 555 ms 17304 KB Output is correct
17 Correct 611 ms 17288 KB Output is correct
18 Correct 581 ms 17316 KB Output is correct
19 Correct 377 ms 16980 KB Output is correct
20 Correct 373 ms 18816 KB Output is correct
21 Correct 393 ms 18732 KB Output is correct
22 Correct 364 ms 18748 KB Output is correct
23 Correct 344 ms 18744 KB Output is correct
24 Correct 363 ms 18940 KB Output is correct
25 Correct 348 ms 18556 KB Output is correct
26 Correct 363 ms 18788 KB Output is correct
27 Correct 357 ms 18772 KB Output is correct
28 Correct 359 ms 18756 KB Output is correct
29 Correct 363 ms 18772 KB Output is correct
30 Correct 378 ms 19248 KB Output is correct
31 Correct 362 ms 19192 KB Output is correct
32 Correct 384 ms 19596 KB Output is correct
33 Correct 431 ms 21400 KB Output is correct
34 Correct 373 ms 23640 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 696 ms 15748 KB Output is correct
5 Correct 797 ms 16268 KB Output is correct
6 Correct 895 ms 18276 KB Output is correct
7 Correct 902 ms 19496 KB Output is correct
8 Correct 890 ms 19572 KB Output is correct
9 Correct 930 ms 19564 KB Output is correct
10 Correct 943 ms 19576 KB Output is correct
11 Correct 943 ms 19796 KB Output is correct
12 Correct 989 ms 19580 KB Output is correct
13 Correct 1010 ms 19568 KB Output is correct
14 Correct 40 ms 11348 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct
18 Correct 2 ms 8708 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 3 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 3 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 2 ms 8536 KB Output is correct
26 Correct 2 ms 8620 KB Output is correct
27 Correct 2 ms 8540 KB Output is correct
28 Correct 2 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct
30 Correct 6 ms 8796 KB Output is correct
31 Correct 7 ms 8796 KB Output is correct
32 Correct 8 ms 8796 KB Output is correct
33 Correct 8 ms 8992 KB Output is correct
34 Correct 8 ms 8796 KB Output is correct
35 Correct 7 ms 8792 KB Output is correct
36 Correct 9 ms 8796 KB Output is correct
37 Correct 7 ms 8796 KB Output is correct
38 Correct 4 ms 8796 KB Output is correct
39 Correct 5 ms 8796 KB Output is correct
40 Correct 4 ms 8796 KB Output is correct
41 Correct 6 ms 8796 KB Output is correct
42 Correct 5 ms 8796 KB Output is correct
43 Correct 4 ms 8796 KB Output is correct
44 Correct 7 ms 8796 KB Output is correct
45 Correct 6 ms 8792 KB Output is correct
46 Correct 6 ms 8796 KB Output is correct
47 Correct 5 ms 8796 KB Output is correct
48 Correct 5 ms 8796 KB Output is correct
49 Correct 5 ms 8796 KB Output is correct
50 Correct 5 ms 8896 KB Output is correct
51 Correct 6 ms 8696 KB Output is correct
52 Correct 5 ms 8796 KB Output is correct
53 Correct 5 ms 8792 KB Output is correct
54 Correct 5 ms 8796 KB Output is correct
55 Correct 5 ms 8796 KB Output is correct
56 Correct 3 ms 8540 KB Output is correct
57 Correct 3 ms 8796 KB Output is correct
58 Correct 7 ms 8796 KB Output is correct
59 Correct 2 ms 8540 KB Output is correct
60 Correct 3 ms 8540 KB Output is correct
61 Correct 3 ms 8536 KB Output is correct
62 Correct 101 ms 19768 KB Output is correct
63 Correct 90 ms 23072 KB Output is correct
64 Correct 106 ms 24916 KB Output is correct
65 Correct 138 ms 27488 KB Output is correct
66 Correct 141 ms 27476 KB Output is correct
67 Correct 143 ms 27440 KB Output is correct
68 Correct 136 ms 27316 KB Output is correct
69 Correct 140 ms 27476 KB Output is correct
70 Correct 139 ms 26196 KB Output is correct
71 Correct 133 ms 26268 KB Output is correct
72 Correct 138 ms 26260 KB Output is correct
73 Correct 53 ms 25288 KB Output is correct
74 Correct 145 ms 27160 KB Output is correct
75 Correct 39 ms 11348 KB Output is correct
76 Correct 3 ms 8544 KB Output is correct
77 Correct 293 ms 13148 KB Output is correct
78 Correct 467 ms 13780 KB Output is correct
79 Correct 357 ms 14236 KB Output is correct
80 Correct 626 ms 16728 KB Output is correct
81 Correct 627 ms 16980 KB Output is correct
82 Correct 610 ms 16980 KB Output is correct
83 Correct 588 ms 16980 KB Output is correct
84 Correct 561 ms 16976 KB Output is correct
85 Correct 590 ms 16984 KB Output is correct
86 Correct 583 ms 17264 KB Output is correct
87 Correct 612 ms 17076 KB Output is correct
88 Correct 618 ms 17328 KB Output is correct
89 Correct 614 ms 18192 KB Output is correct
90 Correct 665 ms 20512 KB Output is correct
91 Correct 555 ms 17304 KB Output is correct
92 Correct 611 ms 17288 KB Output is correct
93 Correct 581 ms 17316 KB Output is correct
94 Correct 377 ms 16980 KB Output is correct
95 Correct 373 ms 18816 KB Output is correct
96 Correct 393 ms 18732 KB Output is correct
97 Correct 364 ms 18748 KB Output is correct
98 Correct 344 ms 18744 KB Output is correct
99 Correct 363 ms 18940 KB Output is correct
100 Correct 348 ms 18556 KB Output is correct
101 Correct 363 ms 18788 KB Output is correct
102 Correct 357 ms 18772 KB Output is correct
103 Correct 359 ms 18756 KB Output is correct
104 Correct 363 ms 18772 KB Output is correct
105 Correct 378 ms 19248 KB Output is correct
106 Correct 362 ms 19192 KB Output is correct
107 Correct 384 ms 19596 KB Output is correct
108 Correct 431 ms 21400 KB Output is correct
109 Correct 373 ms 23640 KB Output is correct
110 Correct 2 ms 8792 KB Output is correct
111 Correct 2 ms 8540 KB Output is correct
112 Correct 3 ms 8540 KB Output is correct
113 Correct 696 ms 15748 KB Output is correct
114 Correct 797 ms 16268 KB Output is correct
115 Correct 895 ms 18276 KB Output is correct
116 Correct 902 ms 19496 KB Output is correct
117 Correct 890 ms 19572 KB Output is correct
118 Correct 930 ms 19564 KB Output is correct
119 Correct 943 ms 19576 KB Output is correct
120 Correct 943 ms 19796 KB Output is correct
121 Correct 989 ms 19580 KB Output is correct
122 Correct 1010 ms 19568 KB Output is correct
123 Correct 40 ms 11348 KB Output is correct
124 Correct 569 ms 22208 KB Output is correct
125 Correct 459 ms 20304 KB Output is correct
126 Correct 661 ms 22612 KB Output is correct
127 Correct 645 ms 22568 KB Output is correct
128 Correct 661 ms 22652 KB Output is correct
129 Correct 707 ms 22492 KB Output is correct
130 Correct 666 ms 22616 KB Output is correct
131 Correct 140 ms 29048 KB Output is correct
132 Correct 170 ms 30420 KB Output is correct
133 Correct 151 ms 26452 KB Output is correct
134 Correct 414 ms 22652 KB Output is correct
135 Correct 405 ms 22620 KB Output is correct
136 Correct 400 ms 22608 KB Output is correct
137 Correct 245 ms 22912 KB Output is correct
138 Correct 236 ms 22812 KB Output is correct
139 Correct 244 ms 22872 KB Output is correct
140 Correct 224 ms 22732 KB Output is correct
141 Correct 284 ms 22868 KB Output is correct
142 Correct 255 ms 22872 KB Output is correct
143 Correct 64 ms 19132 KB Output is correct
144 Correct 646 ms 22248 KB Output is correct