Submission #916669

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916669	2024-01-26T09:04:22 Z	thangdz2k7	Tourism (JOI23_tourism)	C++17	7 / 100	150 ms	27480 KB

tourism

#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 <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){

    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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	8536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	8536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8540 KB	Output is correct
2	Correct	2 ms	8540 KB	Output is correct
3	Correct	2 ms	8540 KB	Output is correct
4	Correct	98 ms	19676 KB	Output is correct
5	Correct	90 ms	23124 KB	Output is correct
6	Correct	106 ms	24900 KB	Output is correct
7	Correct	129 ms	27476 KB	Output is correct
8	Correct	150 ms	27480 KB	Output is correct
9	Correct	129 ms	27396 KB	Output is correct
10	Correct	133 ms	27476 KB	Output is correct
11	Correct	130 ms	27236 KB	Output is correct
12	Correct	132 ms	26284 KB	Output is correct
13	Correct	132 ms	26040 KB	Output is correct
14	Correct	135 ms	26268 KB	Output is correct
15	Correct	54 ms	25292 KB	Output is correct
16	Correct	133 ms	27192 KB	Output is correct
17	Correct	38 ms	11356 KB	Output is correct