oj.uz

답안 #612561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612561 2022-07-29T17:37:42 Z alireza_kaviani 수도 (JOI20_capital_city) C++17
11 / 100
 3000 ms 488948 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 2e5 + 10;
const ll LOG = 18;
const ll MAX = MAXN * LOG + MAXN;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , k , cnt , ans = MOD , C[MAXN] , par[LOG][MAXN] , H[MAXN] , mark[MAX];
vector<int> tree[MAXN] , adj[MAX] , radj[MAX] , vec[MAXN] , ord;

void addEdge(int v , int u){
    adj[v].push_back(u);
    radj[u].push_back(v);
}

void PreDFS(int v , int p = 0){
    par[0][v] = p;
    H[v] = H[p] + 1;
    for(int u : tree[v]){
        if(u == p)  continue;
        PreDFS(u , v);
    }
}

int getPar(int v , int h){
    for(int i = 0 ; i < LOG ; i++){
        if(h & (1 << i)){
            v = par[i][v];
        }
    }
    return v;
}

int LCA(int v , int u){
    if(H[v] > H[u]) swap(v , u);
    u = getPar(u , H[u] - H[v]);
    if(v == u)  return v;
    for(int i = LOG - 1 ; i >= 0 ; i--){
        if(par[i][v] != par[i][u]){
            v = par[i][v];
            u = par[i][u];
        }
    }
    return par[0][v];
}

void add(int x , int v , int h){
    for(int i = 0 ; i < LOG ; i++){
        if(h & (1 << i)){
            addEdge(x , i * MAXN + v);
            v = par[i][v];
        }
    }
}

void DFS(int v){
    mark[v] = 1;
    for(int u : radj[v]){
        if(!mark[u]){
            DFS(u);
        }
    }
    ord.push_back(v);
}

void DFS2(int v){
    if(LOG * MAXN + 1 <= v && v <= LOG * MAXN + k){
        cnt++;
    }
    mark[v] = 1;
    for(int u : adj[v]){
        if(!mark[u]){
            DFS2(u);
        }
    }
}

void DFS3(int v){
    mark[v] = 2;
    for(int u : radj[v]){
        if(mark[u] != 2){
            DFS3(u);
        }
    }
}

void SCC(){
    for(int i = 0 ; i < MAX ; i++){
        if(!mark[i]){
            DFS(i);
        }
    }
    fill(mark , mark + MAX , 0);
    reverse(all(ord));
    for(int i : ord){
        if(mark[i]) continue;
        cnt = 0;
        DFS2(i);
        DFS3(i);
        if(cnt > 0){
            ans = min(ans , cnt);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n >> k;
    for(int i = 1 ; i < n ; i++){
        int v , u;
        cin >> v >> u;
        tree[v].push_back(u);
        tree[u].push_back(v);
    }
    for(int i = 1 ; i <= n ; i++){
        cin >> C[i];
        vec[C[i]].push_back(i);
    }
    PreDFS(1);

    for(int i = 1 ; i < LOG ; i++){
        for(int j = 1 ; j <= n ; j++){
            par[i][j] = par[i - 1][par[i - 1][j]];
            addEdge(i * MAXN + j , (i - 1) * MAXN + j);
            addEdge(i * MAXN + j , (i - 1) * MAXN + par[i - 1][j]);
        }
    }
    for(int i = 1 ; i <= n ; i++){
        addEdge(i , LOG * MAXN + C[i]);
    }

    for(int i = 1 ; i <= k ; i++){
        for(int j = 0 ; j + 1 < SZ(vec[i]) ; j++){
            int v = vec[i][j] , u = vec[i][j + 1];
            int lca = LCA(v , u);
            add(LOG * MAXN + i , v , H[v] - H[lca]);
            add(LOG * MAXN + i , u , H[u] - H[lca]);
            addEdge(LOG * MAXN + i , lca);
        }
    }

    SCC();
    cout << ans - 1 << endl;

    return 0;
}
/*

*/

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 218220 KB Output is correct
2 Correct 178 ms 218124 KB Output is correct
3 Correct 204 ms 218100 KB Output is correct
4 Correct 180 ms 218172 KB Output is correct
5 Correct 233 ms 218196 KB Output is correct
6 Correct 180 ms 218136 KB Output is correct
7 Correct 218 ms 218172 KB Output is correct
8 Correct 186 ms 218156 KB Output is correct
9 Correct 193 ms 218096 KB Output is correct
10 Correct 187 ms 218144 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 218220 KB Output is correct
2 Correct 178 ms 218124 KB Output is correct
3 Correct 204 ms 218100 KB Output is correct
4 Correct 180 ms 218172 KB Output is correct
5 Correct 233 ms 218196 KB Output is correct
6 Correct 180 ms 218136 KB Output is correct
7 Correct 218 ms 218172 KB Output is correct
8 Correct 186 ms 218156 KB Output is correct
9 Correct 193 ms 218096 KB Output is correct
10 Correct 187 ms 218144 KB Output is correct
11 Correct 192 ms 220852 KB Output is correct
12 Correct 199 ms 220840 KB Output is correct
13 Correct 173 ms 220868 KB Output is correct
14 Correct 200 ms 220788 KB Output is correct
15 Correct 194 ms 220824 KB Output is correct
16 Correct 241 ms 220892 KB Output is correct
17 Correct 218 ms 220776 KB Output is correct
18 Correct 215 ms 220744 KB Output is correct
19 Correct 199 ms 220880 KB Output is correct
20 Correct 196 ms 220796 KB Output is correct
21 Correct 209 ms 220824 KB Output is correct
22 Correct 174 ms 220780 KB Output is correct
23 Correct 194 ms 220888 KB Output is correct
24 Correct 196 ms 220820 KB Output is correct
25 Correct 225 ms 220788 KB Output is correct
26 Correct 210 ms 220816 KB Output is correct
27 Correct 208 ms 220832 KB Output is correct
28 Correct 195 ms 220852 KB Output is correct
29 Correct 213 ms 220816 KB Output is correct
30 Correct 183 ms 220832 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3101 ms 488948 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 218220 KB Output is correct
2 Correct 178 ms 218124 KB Output is correct
3 Correct 204 ms 218100 KB Output is correct
4 Correct 180 ms 218172 KB Output is correct
5 Correct 233 ms 218196 KB Output is correct
6 Correct 180 ms 218136 KB Output is correct
7 Correct 218 ms 218172 KB Output is correct
8 Correct 186 ms 218156 KB Output is correct
9 Correct 193 ms 218096 KB Output is correct
10 Correct 187 ms 218144 KB Output is correct
11 Correct 192 ms 220852 KB Output is correct
12 Correct 199 ms 220840 KB Output is correct
13 Correct 173 ms 220868 KB Output is correct
14 Correct 200 ms 220788 KB Output is correct
15 Correct 194 ms 220824 KB Output is correct
16 Correct 241 ms 220892 KB Output is correct
17 Correct 218 ms 220776 KB Output is correct
18 Correct 215 ms 220744 KB Output is correct
19 Correct 199 ms 220880 KB Output is correct
20 Correct 196 ms 220796 KB Output is correct
21 Correct 209 ms 220824 KB Output is correct
22 Correct 174 ms 220780 KB Output is correct
23 Correct 194 ms 220888 KB Output is correct
24 Correct 196 ms 220820 KB Output is correct
25 Correct 225 ms 220788 KB Output is correct
26 Correct 210 ms 220816 KB Output is correct
27 Correct 208 ms 220832 KB Output is correct
28 Correct 195 ms 220852 KB Output is correct
29 Correct 213 ms 220816 KB Output is correct
30 Correct 183 ms 220832 KB Output is correct
31 Execution timed out 3101 ms 488948 KB Time limit exceeded
32 Halted 0 ms 0 KB -