oj.uz

Submission #534539

# Submission time Handle Problem Language Result Execution time Memory
534539 2022-03-08T08:57:58 Z pokmui9909 Capital City (JOI20_capital_city) C++17
0 / 100
 300 ms 118416 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 12996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 12996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 117968 KB Output is correct
2 Correct 189 ms 118128 KB Output is correct
3 Correct 284 ms 118064 KB Output is correct
4 Correct 183 ms 118060 KB Output is correct
5 Correct 297 ms 118124 KB Output is correct
6 Correct 176 ms 118052 KB Output is correct
7 Correct 255 ms 118184 KB Output is correct
8 Correct 177 ms 118212 KB Output is correct
9 Incorrect 242 ms 118416 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 12996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -