oj.uz

Submission #253236

# Submission time Handle Problem Language Result Execution time Memory
253236 2020-07-27T14:12:17 Z egekabas Capital City (JOI20_capital_city) C++14
31 / 100
 609 ms 69236 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<int, int> pii;
typedef pair<ld, ld> pld;
int n, k;
vector<int> g[200009];
int col[200009];
int depth[200009];
int dad[200009][30];
void dfs1(int v, int prt){
    for(int 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);
        }
}
int lca(int x, int y){
    if(depth[x] < depth[y])
        swap(x, y);
    for(int i = 29; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y])
            x = dad[x][i];
    if(x == y) return x;
    for(int i = 29; i >= 0; --i)
        if(dad[x][i] != dad[y][i]){
            x = dad[x][i];
            y = dad[y][i];
        }
    return dad[x][0];
}
int root[200009];
vector<int> con[200009];
vector<int> inc[200009];

void dfs2(int v, int 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]);
            }
        }
}
int vis[200009];
vector<int> order;
void ssc1(int v){
    vis[v] = 1;
    for(auto u : con[v])
        if(vis[u] == 0)
            ssc1(u);
    order.pb(v);
}
int gather(int v){
    int ret = 1;
    vis[v] = 1;
    for(auto u : inc[v])
        if(vis[u] == 0){
            ret += gather(u);
            ret = min(ret, int(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(int i = 0; i < n-1; ++i){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    for(int i = 1; i <= n; ++i)
        cin >> col[i];
    
    depth[1] = 1;
    dfs1(1, 0);
    for(int i = 1; i <= n; ++i){
        if(root[col[i]] == 0)
            root[col[i]] = i;
        else
            root[col[i]] = lca(root[col[i]], i);
    }
    for(int i = 1; i <= k; ++i)
        root[i] = depth[root[i]];
    dfs2(1, 0);
    for(int 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(int i = 1; i <= k; ++i)
        if(vis[i] == 0)
            ssc1(i);
    for(int i = 1; i <= k; ++i) vis[i] = 0;
    int ans = 1e9;
    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 11 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 10 ms 14464 KB Output is correct
7 Correct 11 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 10 ms 14464 KB Output is correct
10 Correct 9 ms 14464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 10 ms 14464 KB Output is correct
7 Correct 11 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 10 ms 14464 KB Output is correct
10 Correct 9 ms 14464 KB Output is correct
11 Incorrect 11 ms 14848 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 493 ms 68724 KB Output is correct
2 Correct 198 ms 69236 KB Output is correct
3 Correct 506 ms 68596 KB Output is correct
4 Correct 201 ms 69196 KB Output is correct
5 Correct 524 ms 65272 KB Output is correct
6 Correct 198 ms 69112 KB Output is correct
7 Correct 609 ms 65272 KB Output is correct
8 Correct 201 ms 68084 KB Output is correct
9 Correct 451 ms 62136 KB Output is correct
10 Correct 546 ms 59768 KB Output is correct
11 Correct 580 ms 62460 KB Output is correct
12 Correct 459 ms 65304 KB Output is correct
13 Correct 589 ms 59384 KB Output is correct
14 Correct 573 ms 65528 KB Output is correct
15 Correct 451 ms 65272 KB Output is correct
16 Correct 506 ms 60300 KB Output is correct
17 Correct 517 ms 60792 KB Output is correct
18 Correct 470 ms 61048 KB Output is correct
19 Correct 560 ms 64120 KB Output is correct
20 Correct 468 ms 66296 KB Output is correct
21 Correct 13 ms 14464 KB Output is correct

Subtask #4
0 / 59.0

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