Submission #534539

#	Time	Username	Problem	Language	Result	Execution time	Memory
534539		pokmui9909	Capital City (JOI20_capital_city)	C++17	0 / 100	300 ms	118416 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node{
    ll l, r, v;
}T[40000005];
ll PST[4000005], num = 0;
void update(ll pv, ll nw, ll s, ll e, ll k, ll v){
    T[nw].v = T[pv].v + v;
    if(s == e) return;
    ll m = (s + e) / 2;
    if(k <= m){
        T[nw].l = ++num, T[nw].r = T[pv].r;
        update(T[pv].l, T[nw].l, s, m, k, v);
    } else {
        T[nw].l = T[pv].l, T[nw].r = ++num;
        update(T[pv].r, T[nw].r, m + 1, e, k, v);
    }
}
ll query(ll node, ll s, ll e, ll l, ll r){
    if(e < l || s > r) return 0;
    if(l <= s && e <= r) return T[node].v;
    ll m = (s + e) / 2;
    return query(T[node].l, s, m, l, r) + query(T[node].r, m + 1, e, l, r);
}

ll N, K;
vector<ll> G[200005];
ll _C[200005];
ll  C[200005];
ll ord[200005], ord_num = 0;
ll L[200005], R[200005];
ll P[200005];
ll A[200005];
void dfs(ll u, ll p){
    ord[u] = ++ord_num;
    for(auto v : G[u]) if(v != p) dfs(v, u);
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    fill(L, L + 200005, 1e15);
    cin >> N >> K;
    for(int i = 1; i < N; i++){
        ll u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ll s = 0;
    for(int i = 1; i <= N; i++){
        assert(G[i].size() <= 2);
        cin >> _C[i];
        if(G[i].size() == 1) s = i;
    }
    dfs(s, -1);
    for(ll i = 1; i <= N; i++){
        C[ord[i]] = _C[i];
        P[i] = N + 1;
    }
    for(ll i = 1; i <= N; i++){
        L[C[i]] = min(L[C[i]], i);
        R[C[i]] = max(R[C[i]], i);
    }
    for(int i = N; i >= 1; i--){
        A[i] = P[C[i]];
        P[C[i]] = i;
    }
    for(int i = 1; i <= N; i++){
        PST[i] = ++num;
        update(PST[i - 1], PST[i], 1, N + 1, A[i], 1);
    }   
    ll ans = 1e15;
    for(int i = 1; i <= K; i++){
        ll l = L[i], r = R[i];
        ans = min(ans, query(PST[r], 1, N + 1, r + 1, N + 1) - query(PST[l - 1], 1, N + 1, r + 1, N + 1));
    }
    cout << ans - 1;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59