Submission #916656

#	Time	Username	Problem	Language	Result	Execution time	Memory
916656		thangdz2k7	Tourism (JOI23_tourism)	C++17	34 / 100	5053 ms	41788 KiB

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 <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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 41