oj.uz

Submission #916656

# Submission time Handle Problem Language Result Execution time Memory
916656 2024-01-26T08:44:52 Z thangdz2k7 Tourism (JOI23_tourism) C++17
34 / 100
 5000 ms 41788 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 = 0;
    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){
            cur = maxsz;
            heavy[u] = v;

        }
    }

    return sz;
}

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

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

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

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

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

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

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

    s[t].insert(iii(ii(l, r), 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(head[v], pos[head[v]], pos[v], val);

    }

    if (depth[u] > depth[v]) swap(u, v);
    add(head[u], 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);

    for (int i = 1; i <= n; ++ i) s[i].insert(iii(ii(0, 0), 0)), s[i].insert(iii(ii(n + 1, n + 1), 0));

    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 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12840 KB Output is correct
8 Correct 4 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 3 ms 12636 KB Output is correct
11 Correct 5 ms 12632 KB Output is correct
12 Correct 3 ms 12636 KB Output is correct
13 Correct 4 ms 12636 KB Output is correct
14 Correct 3 ms 12636 KB Output is correct
15 Correct 6 ms 12636 KB Output is correct
16 Correct 5 ms 12636 KB Output is correct
17 Correct 5 ms 12636 KB Output is correct
18 Correct 4 ms 12636 KB Output is correct
19 Correct 5 ms 12636 KB Output is correct
20 Correct 5 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 3 ms 12636 KB Output is correct
23 Correct 3 ms 12636 KB Output is correct
24 Correct 3 ms 12728 KB Output is correct
25 Correct 3 ms 12636 KB Output is correct
26 Correct 3 ms 12636 KB Output is correct
27 Correct 3 ms 12636 KB Output is correct
28 Correct 3 ms 12636 KB Output is correct
29 Correct 4 ms 12728 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12840 KB Output is correct
8 Correct 4 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 3 ms 12636 KB Output is correct
11 Correct 5 ms 12632 KB Output is correct
12 Correct 3 ms 12636 KB Output is correct
13 Correct 4 ms 12636 KB Output is correct
14 Correct 3 ms 12636 KB Output is correct
15 Correct 6 ms 12636 KB Output is correct
16 Correct 5 ms 12636 KB Output is correct
17 Correct 5 ms 12636 KB Output is correct
18 Correct 4 ms 12636 KB Output is correct
19 Correct 5 ms 12636 KB Output is correct
20 Correct 5 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 3 ms 12636 KB Output is correct
23 Correct 3 ms 12636 KB Output is correct
24 Correct 3 ms 12728 KB Output is correct
25 Correct 3 ms 12636 KB Output is correct
26 Correct 3 ms 12636 KB Output is correct
27 Correct 3 ms 12636 KB Output is correct
28 Correct 3 ms 12636 KB Output is correct
29 Correct 4 ms 12728 KB Output is correct
30 Correct 6 ms 13148 KB Output is correct
31 Correct 6 ms 13148 KB Output is correct
32 Correct 7 ms 13148 KB Output is correct
33 Correct 7 ms 13148 KB Output is correct
34 Correct 7 ms 13140 KB Output is correct
35 Correct 7 ms 13148 KB Output is correct
36 Correct 7 ms 13296 KB Output is correct
37 Correct 8 ms 13148 KB Output is correct
38 Correct 96 ms 13656 KB Output is correct
39 Correct 96 ms 13420 KB Output is correct
40 Correct 95 ms 13404 KB Output is correct
41 Correct 97 ms 13404 KB Output is correct
42 Correct 96 ms 13416 KB Output is correct
43 Correct 102 ms 13368 KB Output is correct
44 Correct 48 ms 13148 KB Output is correct
45 Correct 40 ms 13356 KB Output is correct
46 Correct 45 ms 13148 KB Output is correct
47 Correct 42 ms 13340 KB Output is correct
48 Correct 41 ms 13316 KB Output is correct
49 Correct 47 ms 13324 KB Output is correct
50 Correct 5 ms 13148 KB Output is correct
51 Correct 5 ms 13252 KB Output is correct
52 Correct 5 ms 13148 KB Output is correct
53 Correct 5 ms 13148 KB Output is correct
54 Correct 5 ms 13148 KB Output is correct
55 Correct 5 ms 13148 KB Output is correct
56 Correct 4 ms 12636 KB Output is correct
57 Correct 4 ms 13148 KB Output is correct
58 Correct 8 ms 13404 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 5 ms 12792 KB Output is correct
4 Execution timed out 5012 ms 33604 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 161 ms 26056 KB Output is correct
3 Correct 259 ms 27272 KB Output is correct
4 Correct 248 ms 29164 KB Output is correct
5 Correct 376 ms 36692 KB Output is correct
6 Correct 393 ms 36692 KB Output is correct
7 Correct 398 ms 36692 KB Output is correct
8 Correct 377 ms 36692 KB Output is correct
9 Correct 412 ms 36948 KB Output is correct
10 Correct 392 ms 36924 KB Output is correct
11 Correct 420 ms 37148 KB Output is correct
12 Correct 413 ms 37048 KB Output is correct
13 Correct 446 ms 37404 KB Output is correct
14 Correct 394 ms 38516 KB Output is correct
15 Correct 416 ms 41788 KB Output is correct
16 Correct 396 ms 37204 KB Output is correct
17 Correct 422 ms 37448 KB Output is correct
18 Correct 470 ms 37380 KB Output is correct
19 Execution timed out 5053 ms 36948 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12644 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 5 ms 12892 KB Output is correct
4 Correct 353 ms 30336 KB Output is correct
5 Correct 332 ms 30548 KB Output is correct
6 Correct 477 ms 37204 KB Output is correct
7 Correct 457 ms 40788 KB Output is correct
8 Correct 491 ms 40784 KB Output is correct
9 Correct 470 ms 40804 KB Output is correct
10 Correct 491 ms 40808 KB Output is correct
11 Correct 461 ms 40820 KB Output is correct
12 Correct 517 ms 40812 KB Output is correct
13 Correct 483 ms 40700 KB Output is correct
14 Correct 42 ms 16980 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12840 KB Output is correct
8 Correct 4 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 3 ms 12636 KB Output is correct
11 Correct 5 ms 12632 KB Output is correct
12 Correct 3 ms 12636 KB Output is correct
13 Correct 4 ms 12636 KB Output is correct
14 Correct 3 ms 12636 KB Output is correct
15 Correct 6 ms 12636 KB Output is correct
16 Correct 5 ms 12636 KB Output is correct
17 Correct 5 ms 12636 KB Output is correct
18 Correct 4 ms 12636 KB Output is correct
19 Correct 5 ms 12636 KB Output is correct
20 Correct 5 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 3 ms 12636 KB Output is correct
23 Correct 3 ms 12636 KB Output is correct
24 Correct 3 ms 12728 KB Output is correct
25 Correct 3 ms 12636 KB Output is correct
26 Correct 3 ms 12636 KB Output is correct
27 Correct 3 ms 12636 KB Output is correct
28 Correct 3 ms 12636 KB Output is correct
29 Correct 4 ms 12728 KB Output is correct
30 Correct 6 ms 13148 KB Output is correct
31 Correct 6 ms 13148 KB Output is correct
32 Correct 7 ms 13148 KB Output is correct
33 Correct 7 ms 13148 KB Output is correct
34 Correct 7 ms 13140 KB Output is correct
35 Correct 7 ms 13148 KB Output is correct
36 Correct 7 ms 13296 KB Output is correct
37 Correct 8 ms 13148 KB Output is correct
38 Correct 96 ms 13656 KB Output is correct
39 Correct 96 ms 13420 KB Output is correct
40 Correct 95 ms 13404 KB Output is correct
41 Correct 97 ms 13404 KB Output is correct
42 Correct 96 ms 13416 KB Output is correct
43 Correct 102 ms 13368 KB Output is correct
44 Correct 48 ms 13148 KB Output is correct
45 Correct 40 ms 13356 KB Output is correct
46 Correct 45 ms 13148 KB Output is correct
47 Correct 42 ms 13340 KB Output is correct
48 Correct 41 ms 13316 KB Output is correct
49 Correct 47 ms 13324 KB Output is correct
50 Correct 5 ms 13148 KB Output is correct
51 Correct 5 ms 13252 KB Output is correct
52 Correct 5 ms 13148 KB Output is correct
53 Correct 5 ms 13148 KB Output is correct
54 Correct 5 ms 13148 KB Output is correct
55 Correct 5 ms 13148 KB Output is correct
56 Correct 4 ms 12636 KB Output is correct
57 Correct 4 ms 13148 KB Output is correct
58 Correct 8 ms 13404 KB Output is correct
59 Correct 3 ms 12632 KB Output is correct
60 Correct 4 ms 12636 KB Output is correct
61 Correct 5 ms 12792 KB Output is correct
62 Execution timed out 5012 ms 33604 KB Time limit exceeded
63 Halted 0 ms 0 KB -