oj.uz

Submission #253239

# Submission time Handle Problem Language Result Execution time Memory
253239 2020-07-27T14:14:15 Z egekabas Capital City (JOI20_capital_city) C++14
31 / 100
 629 ms 92064 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]){
                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);
    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);
    }
    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 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 8 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 11 ms 14464 KB Output is correct
10 Correct 10 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 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 8 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 11 ms 14464 KB Output is correct
10 Correct 10 ms 14464 KB Output is correct
11 Incorrect 13 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 557 ms 92064 KB Output is correct
2 Correct 233 ms 92056 KB Output is correct
3 Correct 562 ms 91796 KB Output is correct
4 Correct 230 ms 92016 KB Output is correct
5 Correct 551 ms 88876 KB Output is correct
6 Correct 291 ms 91892 KB Output is correct
7 Correct 526 ms 88832 KB Output is correct
8 Correct 271 ms 90736 KB Output is correct
9 Correct 506 ms 85620 KB Output is correct
10 Correct 614 ms 83892 KB Output is correct
11 Correct 568 ms 86148 KB Output is correct
12 Correct 629 ms 88180 KB Output is correct
13 Correct 566 ms 83444 KB Output is correct
14 Correct 530 ms 88312 KB Output is correct
15 Correct 499 ms 88180 KB Output is correct
16 Correct 471 ms 84088 KB Output is correct
17 Correct 486 ms 84748 KB Output is correct
18 Correct 483 ms 84724 KB Output is correct
19 Correct 484 ms 87416 KB Output is correct
20 Correct 499 ms 88812 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 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 8 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 11 ms 14464 KB Output is correct
10 Correct 10 ms 14464 KB Output is correct
11 Incorrect 13 ms 15104 KB Output isn't correct
12 Halted 0 ms 0 KB -