oj.uz

Submission #623491

# Submission time Handle Problem Language Result Execution time Memory
623491 2022-08-05T16:55:48 Z welleyth Capital City (JOI20_capital_city) C++17
1 / 100
 3000 ms 41008 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

constexpr int INF = (int)2e18;
constexpr int N = (int)2e5 + 111;
constexpr int md = (int)998244353;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr double eps = 1e-7;

typedef __int128 _uint;
typedef long long ll;

mt19937_64 rnd(time(nullptr));

void add(int& a,int b){
    a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b; while(a < 0) a += md;
}
void add(__int128& a,int b){
    a += b;
}
void sub(__int128& a,int b){
    a -= b;
}

int bpow(int a,int b){
    if(b == 0)
        return 1;
    if(b % 2 == 0){
        int t = bpow(a,b>>1);
        return 1ll*t*t%md;
    }
    return 1ll * a*bpow(a,b-1) % md;
}

int inv(int a){
    return bpow(a,md-2);
}

int fac[N],invfac[N];

void init(){
    fac[0] = 1;
    for(int i = 1; i < N; i++){
        fac[i] = (fac[i-1] * i) % md;
    }
    invfac[N-1] = inv(fac[N-1]);
    for(int i = N-2; i >= 0; i--){
        invfac[i] = (invfac[i+1] * (i+1))%md;
    }
    return;
}

//int C(int n,int k){
//    if(k > n)
//        return 0;
//    return fac[n] * invfac[k] % md * invfac[n-k] % md;
//}
//
//int A(int n,int k){
//    if(k > n)
//        return 0;
//    return fac[n] * invfac[n-k] % md;
//}

vector<int> g[N];
int col[N];
vector<int> cities[N];
int sz[N];
int ans = INF;
bool used[N];
bool choosen[N];
int p[N];
int L[N];
int d[N];

void dfs1(int v,int pr = -1){
    sz[v] = 1;
    for(auto& to : g[v]){
        if(to == pr || used[to])
            continue;
        dfs1(to,v);
        sz[v] += sz[to];
    }
    return;
}

int getCentroid(int v,int n,int pr = -1){
    for(auto& to : g[v]){
        if(to == pr || used[to])
            continue;
        if(sz[to] >= n/2)
            return getCentroid(to,n,v);
    }
    return v;
}

int CNT = 0;
void dfs3(int v,int pr = -1){
    L[v] = CNT;
    for(auto& to : g[v]){
        if(to == pr || used[to])
            continue;
        p[to] = v;
        d[to] = d[v] + 1;
        dfs3(to,v);
    }
    return;
}

void solve(int v,int pr = -1){
    dfs1(v);
    int C = getCentroid(v,sz[v]);
//    cerr << "C = " << C <<s "\n";
    used[C] = true;
    int cur_col = col[C];
    dfs1(C);
    CNT++;
    d[C] = 0;
    dfs3(C);
//    cerr << "ok\n";
    if(!choosen[cur_col]){
        set<int> added_colors;
        added_colors.insert(cur_col);
        set<pair<int,int>> q;
        bool ok = true;
        set<int> visited;
        for(auto& x : cities[cur_col]){
            q.insert(mp(-d[x],x));
            visited.insert(x);
            if(L[x] != CNT){
                ok = false;
                break;
            }
        }
        while(!q.empty() && ok){
            int v = q.begin()->second;
            q.erase(q.begin());
//            cerr << "v = " << v << "\n";
            if(choosen[col[v]]){
                ok = false;
                break;
            }
            if(!added_colors.count(col[v])){
                for(auto& x : cities[col[v]]){
                    if(!visited.count(x)){
                        q.insert(mp(-d[x],x));
                        visited.insert(x);
                    }
                    if(L[x] != CNT){
                        ok = false;
                    }
                }
                added_colors.insert(col[v]);
            }
            if(p[v] > 0 && !visited.count(p[v])){
                q.insert(mp(-d[p[v]],p[v]));
                visited.insert(p[v]);
            }
        }
        if(ok){
            ans = min(ans,(int)added_colors.size()-1);
            choosen[cur_col] = 1;
        }
//        cerr << "v = " << v << ", centroid = " << C << "\n";
    }
    for(auto& to : g[C]){
        if(!used[to]){
            solve(to);
        }
    }
    return;
}

void solve(){
    int n,k;
    cin >> n >> k;

    for(int i = 1; i < n; i++){
        int a,b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    for(int i = 1; i <= n; i++){
        cin >> col[i];
        cities[col[i]].pb(i);
    }

    solve(1);

    assert(ans != INF);
    cout << ans << "\n";

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    init();
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
//        cerr << "test = " << test << "\n";
        solve();
    }
    return 0;
}
/**

**/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12884 KB Output is correct
2 Correct 11 ms 12884 KB Output is correct
3 Correct 9 ms 12816 KB Output is correct
4 Correct 11 ms 12816 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 8 ms 12884 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12884 KB Output is correct
9 Correct 9 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12884 KB Output is correct
2 Correct 11 ms 12884 KB Output is correct
3 Correct 9 ms 12816 KB Output is correct
4 Correct 11 ms 12816 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 8 ms 12884 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12884 KB Output is correct
9 Correct 9 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct
11 Correct 10 ms 13248 KB Output is correct
12 Correct 11 ms 13208 KB Output is correct
13 Correct 11 ms 13192 KB Output is correct
14 Correct 12 ms 13248 KB Output is correct
15 Correct 14 ms 13156 KB Output is correct
16 Correct 13 ms 13012 KB Output is correct
17 Correct 10 ms 13196 KB Output is correct
18 Correct 10 ms 13228 KB Output is correct
19 Correct 12 ms 13152 KB Output is correct
20 Correct 11 ms 13268 KB Output is correct
21 Correct 10 ms 13140 KB Output is correct
22 Correct 10 ms 13044 KB Output is correct
23 Correct 9 ms 13012 KB Output is correct
24 Correct 12 ms 13144 KB Output is correct
25 Correct 16 ms 13100 KB Output is correct
26 Correct 20 ms 13140 KB Output is correct
27 Correct 16 ms 13212 KB Output is correct
28 Incorrect 14 ms 13140 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 35960 KB Output is correct
2 Correct 235 ms 36252 KB Output is correct
3 Correct 601 ms 35932 KB Output is correct
4 Correct 256 ms 36164 KB Output is correct
5 Correct 631 ms 36304 KB Output is correct
6 Correct 250 ms 36376 KB Output is correct
7 Correct 641 ms 37692 KB Output is correct
8 Correct 287 ms 40088 KB Output is correct
9 Execution timed out 3091 ms 41008 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12884 KB Output is correct
2 Correct 11 ms 12884 KB Output is correct
3 Correct 9 ms 12816 KB Output is correct
4 Correct 11 ms 12816 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 8 ms 12884 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12884 KB Output is correct
9 Correct 9 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct
11 Correct 10 ms 13248 KB Output is correct
12 Correct 11 ms 13208 KB Output is correct
13 Correct 11 ms 13192 KB Output is correct
14 Correct 12 ms 13248 KB Output is correct
15 Correct 14 ms 13156 KB Output is correct
16 Correct 13 ms 13012 KB Output is correct
17 Correct 10 ms 13196 KB Output is correct
18 Correct 10 ms 13228 KB Output is correct
19 Correct 12 ms 13152 KB Output is correct
20 Correct 11 ms 13268 KB Output is correct
21 Correct 10 ms 13140 KB Output is correct
22 Correct 10 ms 13044 KB Output is correct
23 Correct 9 ms 13012 KB Output is correct
24 Correct 12 ms 13144 KB Output is correct
25 Correct 16 ms 13100 KB Output is correct
26 Correct 20 ms 13140 KB Output is correct
27 Correct 16 ms 13212 KB Output is correct
28 Incorrect 14 ms 13140 KB Output isn't correct
29 Halted 0 ms 0 KB -