oj.uz

답안 #253235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253235 2020-07-27T14:10:52 Z egekabas 수도 (JOI20_capital_city) C++14
1 / 100
 570 ms 72692 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);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 8 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 9 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 8 ms 14464 KB Output is correct
10 Correct 8 ms 14492 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 8 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 9 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 8 ms 14464 KB Output is correct
10 Correct 8 ms 14492 KB Output is correct
11 Incorrect 10 ms 14848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 476 ms 68644 KB Output is correct
2 Correct 195 ms 72692 KB Output is correct
3 Correct 452 ms 71924 KB Output is correct
4 Correct 187 ms 72692 KB Output is correct
5 Correct 461 ms 68604 KB Output is correct
6 Correct 194 ms 72568 KB Output is correct
7 Correct 509 ms 68676 KB Output is correct
8 Correct 195 ms 71412 KB Output is correct
9 Correct 426 ms 65528 KB Output is correct
10 Correct 438 ms 63224 KB Output is correct
11 Correct 417 ms 65912 KB Output is correct
12 Correct 442 ms 68728 KB Output is correct
13 Correct 412 ms 62716 KB Output is correct
14 Correct 457 ms 68912 KB Output is correct
15 Correct 427 ms 68600 KB Output is correct
16 Correct 450 ms 63800 KB Output is correct
17 Correct 570 ms 64376 KB Output is correct
18 Correct 434 ms 64288 KB Output is correct
19 Correct 502 ms 67576 KB Output is correct
20 Incorrect 439 ms 69624 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 8 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 9 ms 14464 KB Output is correct
8 Correct 9 ms 14464 KB Output is correct
9 Correct 8 ms 14464 KB Output is correct
10 Correct 8 ms 14492 KB Output is correct
11 Incorrect 10 ms 14848 KB Output isn't correct
12 Halted 0 ms 0 KB -