oj.uz

Submission #253243

# Submission time Handle Problem Language Result Execution time Memory
253243 2020-07-27T14:17:32 Z egekabas Capital City (JOI20_capital_city) C++14
31 / 100
 703 ms 92028 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);
    assert(ans < 1e9-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 8 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 8 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 9 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 8 ms 14464 KB Output is correct
9 Correct 8 ms 14464 KB Output is correct
10 Correct 12 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 11 ms 14464 KB Output is correct
4 Correct 8 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 9 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 8 ms 14464 KB Output is correct
9 Correct 8 ms 14464 KB Output is correct
10 Correct 12 ms 14464 KB Output is correct
11 Incorrect 15 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 633 ms 92028 KB Output is correct
2 Correct 245 ms 92016 KB Output is correct
3 Correct 570 ms 91764 KB Output is correct
4 Correct 243 ms 92016 KB Output is correct
5 Correct 571 ms 89328 KB Output is correct
6 Correct 248 ms 91920 KB Output is correct
7 Correct 563 ms 88816 KB Output is correct
8 Correct 248 ms 90860 KB Output is correct
9 Correct 557 ms 87640 KB Output is correct
10 Correct 534 ms 85600 KB Output is correct
11 Correct 553 ms 88100 KB Output is correct
12 Correct 597 ms 90116 KB Output is correct
13 Correct 548 ms 85452 KB Output is correct
14 Correct 553 ms 90156 KB Output is correct
15 Correct 608 ms 90484 KB Output is correct
16 Correct 541 ms 86244 KB Output is correct
17 Correct 564 ms 86880 KB Output is correct
18 Correct 551 ms 86868 KB Output is correct
19 Correct 703 ms 89564 KB Output is correct
20 Correct 534 ms 91132 KB Output is correct
21 Correct 11 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 11 ms 14464 KB Output is correct
4 Correct 8 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 9 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 8 ms 14464 KB Output is correct
9 Correct 8 ms 14464 KB Output is correct
10 Correct 12 ms 14464 KB Output is correct
11 Incorrect 15 ms 15104 KB Output isn't correct
12 Halted 0 ms 0 KB -