oj.uz

답안 #623487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623487 2022-08-05T16:50:54 Z welleyth 수도 (JOI20_capital_city) C++17
1 / 100
 3000 ms 40864 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]);
            }
        }
        if(ok) {
            ans = min(ans,(int)added_colors.size()-1);
            choosen[cur_col] = 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);

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

**/

Compilation message

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

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 8 ms 12876 KB Output is correct
4 Correct 8 ms 12804 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 8 ms 12876 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12872 KB Output is correct
9 Correct 10 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 8 ms 12876 KB Output is correct
4 Correct 8 ms 12804 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 8 ms 12876 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12872 KB Output is correct
9 Correct 10 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct
11 Correct 11 ms 13184 KB Output is correct
12 Correct 11 ms 13140 KB Output is correct
13 Correct 11 ms 13268 KB Output is correct
14 Correct 12 ms 13172 KB Output is correct
15 Correct 11 ms 13024 KB Output is correct
16 Correct 10 ms 13120 KB Output is correct
17 Correct 10 ms 13212 KB Output is correct
18 Incorrect 10 ms 13152 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 638 ms 35988 KB Output is correct
2 Correct 228 ms 36172 KB Output is correct
3 Correct 596 ms 35948 KB Output is correct
4 Correct 244 ms 36260 KB Output is correct
5 Correct 605 ms 36364 KB Output is correct
6 Correct 234 ms 36344 KB Output is correct
7 Correct 649 ms 37692 KB Output is correct
8 Correct 279 ms 40116 KB Output is correct
9 Execution timed out 3098 ms 40864 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 8 ms 12876 KB Output is correct
4 Correct 8 ms 12804 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 8 ms 12876 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12872 KB Output is correct
9 Correct 10 ms 12884 KB Output is correct
10 Correct 8 ms 12884 KB Output is correct
11 Correct 11 ms 13184 KB Output is correct
12 Correct 11 ms 13140 KB Output is correct
13 Correct 11 ms 13268 KB Output is correct
14 Correct 12 ms 13172 KB Output is correct
15 Correct 11 ms 13024 KB Output is correct
16 Correct 10 ms 13120 KB Output is correct
17 Correct 10 ms 13212 KB Output is correct
18 Incorrect 10 ms 13152 KB Output isn't correct
19 Halted 0 ms 0 KB -