oj.uz

Submission #623485

# Submission time Handle Problem Language Result Execution time Memory
623485 2022-08-05T16:48:33 Z welleyth Capital City (JOI20_capital_city) C++17
1 / 100
 990 ms 41004 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,pr);
    int C = getCentroid(v,sz[v],pr);
//    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]);
            }
        }
        choosen[cur_col] = 1;
        if(ok)
            ans = min(ans,(int)added_colors.size()-1);
//        cerr << "v = " << v << ", centroid = " << C << "\n";
    }
    f:;
    for(auto& to : g[C]){
        if(!used[to]){
            solve(to,v);
        }
    }
    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);

    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;
}
/**

**/

Compilation message

capital_city.cpp: In function 'void solve(long long int, long long int)':
capital_city.cpp:179:5: warning: label 'f' defined but not used [-Wunused-label]
  179 |     f:;
      |     ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12884 KB Output is correct
2 Correct 9 ms 12808 KB Output is correct
3 Correct 10 ms 12884 KB Output is correct
4 Correct 8 ms 12872 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 12868 KB Output is correct
9 Correct 8 ms 12884 KB Output is correct
10 Correct 8 ms 12776 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 9 ms 12808 KB Output is correct
3 Correct 10 ms 12884 KB Output is correct
4 Correct 8 ms 12872 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 12868 KB Output is correct
9 Correct 8 ms 12884 KB Output is correct
10 Correct 8 ms 12776 KB Output is correct
11 Correct 10 ms 13140 KB Output is correct
12 Correct 11 ms 13164 KB Output is correct
13 Correct 10 ms 13140 KB Output is correct
14 Correct 11 ms 13224 KB Output is correct
15 Correct 13 ms 13012 KB Output is correct
16 Correct 11 ms 13028 KB Output is correct
17 Correct 10 ms 13264 KB Output is correct
18 Incorrect 10 ms 13140 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 36088 KB Output is correct
2 Correct 211 ms 36360 KB Output is correct
3 Correct 547 ms 35964 KB Output is correct
4 Correct 217 ms 36216 KB Output is correct
5 Correct 589 ms 36288 KB Output is correct
6 Correct 214 ms 36556 KB Output is correct
7 Correct 586 ms 37708 KB Output is correct
8 Correct 265 ms 40204 KB Output is correct
9 Correct 977 ms 41004 KB Output is correct
10 Incorrect 990 ms 40196 KB Output isn't correct
11 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 9 ms 12808 KB Output is correct
3 Correct 10 ms 12884 KB Output is correct
4 Correct 8 ms 12872 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 12868 KB Output is correct
9 Correct 8 ms 12884 KB Output is correct
10 Correct 8 ms 12776 KB Output is correct
11 Correct 10 ms 13140 KB Output is correct
12 Correct 11 ms 13164 KB Output is correct
13 Correct 10 ms 13140 KB Output is correct
14 Correct 11 ms 13224 KB Output is correct
15 Correct 13 ms 13012 KB Output is correct
16 Correct 11 ms 13028 KB Output is correct
17 Correct 10 ms 13264 KB Output is correct
18 Incorrect 10 ms 13140 KB Output isn't correct
19 Halted 0 ms 0 KB -