oj.uz

Submission #253242

# Submission time Handle Problem Language Result Execution time Memory
253242 2020-07-27T14:16:45 Z egekabas Capital City (JOI20_capital_city) C++14
31 / 100
 812 ms 92140 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, k;
vector<ll> g[200009];
ll col[200009];
ll depth[200009];
ll dad[200009][30];
void dfs1(ll v, ll prt){
    for(ll i = 1; i < 30; ++i)
        dad[v][i] = dad[dad[v][i-1]][i-1];
    for(auto u : g[v])
        if(u != prt){
            depth[u] = depth[v]+1;
            dad[u][0] = v;
            dfs1(u, v);
        }
}
ll lca(ll x, ll y){
    if(depth[x] < depth[y])
        swap(x, y);
    for(ll i = 29; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y])
            x = dad[x][i];
    if(x == y) return x;
    for(ll i = 29; i >= 0; --i)
        if(dad[x][i] != dad[y][i]){
            x = dad[x][i];
            y = dad[y][i];
        }
    return dad[x][0];
}
ll root[200009];
vector<ll> con[200009];
vector<ll> inc[200009];

void dfs2(ll v, ll prt){
    for(auto u : g[v])
        if(u != prt){
            dfs2(u, v);
            if(col[u] != col[v] && root[col[u]] != depth[u]){
                root[col[u]] = min(root[col[u]], root[col[v]]);
                con[col[u]].pb(col[v]);
            }
        }
}
ll vis[200009];
vector<ll> order;
void ssc1(ll v){
    vis[v] = 1;
    for(auto u : con[v])
        if(vis[u] == 0)
            ssc1(u);
    order.pb(v);
}
ll gather(ll v){
    ll ret = 1;
    vis[v] = 1;
    for(auto u : inc[v])
        if(vis[u] == 0){
            ret += gather(u);
            ret = min(ret, ll(1e9));
        }
    for(auto u : con[v])
        if(vis[u] == 0)
            ret = 1e9;
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> k;
    for(ll i = 0; i < n-1; ++i){
        ll x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    for(ll i = 1; i <= n; ++i)
        cin >> col[i];
    
    depth[1] = 1;
    dfs1(1, 0);
    for(ll i = 1; i <= n; ++i){
        if(root[col[i]] == 0)
            root[col[i]] = i;
        else
            root[col[i]] = lca(root[col[i]], i);
    }
    for(ll i = 1; i <= k; ++i)
        root[i] = depth[root[i]];
    dfs2(1, 0);
    dfs2(1, 0);

    for(ll i = 1; i <= k; ++i){
        sort(con[i].begin(), con[i].end());
        con[i].resize(unique(con[i].begin(), con[i].end())-con[i].begin());
        for(auto u : con[i])
            inc[u].pb(i);
    }
    for(ll i = 1; i <= k; ++i)
        if(vis[i] == 0)
            ssc1(i);
    for(ll i = 1; i <= k; ++i) vis[i] = 0;
    ll ans = k-1;
    reverse(order.begin(), order.end());
    for(auto u : order){
        if(vis[u] == 0)
            ans = min(ans, gather(u)-1);
    }
    assert(ans >= 0);
    cout << ans << '\n';
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 8 ms 14464 KB Output is correct
3 Correct 8 ms 14464 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 9 ms 14464 KB Output is correct
7 Correct 8 ms 14464 KB Output is correct
8 Correct 8 ms 14464 KB Output is correct
9 Correct 9 ms 14464 KB Output is correct
10 Correct 8 ms 14464 KB Output is correct
11 Incorrect 11 ms 15104 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 92008 KB Output is correct
2 Correct 254 ms 92016 KB Output is correct
3 Correct 812 ms 91796 KB Output is correct
4 Correct 250 ms 92140 KB Output is correct
5 Correct 613 ms 89244 KB Output is correct
6 Correct 257 ms 91892 KB Output is correct
7 Correct 554 ms 88816 KB Output is correct
8 Correct 242 ms 90736 KB Output is correct
9 Correct 506 ms 87668 KB Output is correct
10 Correct 504 ms 85600 KB Output is correct
11 Correct 520 ms 87892 KB Output is correct
12 Correct 507 ms 90088 KB Output is correct
13 Correct 514 ms 85364 KB Output is correct
14 Correct 509 ms 90200 KB Output is correct
15 Correct 731 ms 90356 KB Output is correct
16 Correct 519 ms 86316 KB Output is correct
17 Correct 514 ms 86756 KB Output is correct
18 Correct 562 ms 86740 KB Output is correct
19 Correct 545 ms 89732 KB Output is correct
20 Correct 536 ms 91096 KB Output is correct
21 Correct 8 ms 14464 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 8 ms 14464 KB Output is correct
3 Correct 8 ms 14464 KB Output is correct
4 Correct 9 ms 14444 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 9 ms 14464 KB Output is correct
7 Correct 8 ms 14464 KB Output is correct
8 Correct 8 ms 14464 KB Output is correct
9 Correct 9 ms 14464 KB Output is correct
10 Correct 8 ms 14464 KB Output is correct
11 Incorrect 11 ms 15104 KB Output isn't correct
12 Halted 0 ms 0 KB -