oj.uz

Submission #612557

# Submission time Handle Problem Language Result Execution time Memory
612557 2022-07-29T17:33:39 Z alireza_kaviani Capital City (JOI20_capital_city) C++17
11 / 100
 2620 ms 524288 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;
const ll LOG = 20;
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

# Verdict Execution time Memory Grader output
1 Correct 235 ms 256556 KB Output is correct
2 Correct 216 ms 256416 KB Output is correct
3 Correct 204 ms 256488 KB Output is correct
4 Correct 231 ms 256408 KB Output is correct
5 Correct 209 ms 256520 KB Output is correct
6 Correct 230 ms 256416 KB Output is correct
7 Correct 231 ms 256512 KB Output is correct
8 Correct 217 ms 256540 KB Output is correct
9 Correct 212 ms 256444 KB Output is correct
10 Correct 190 ms 256408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 256556 KB Output is correct
2 Correct 216 ms 256416 KB Output is correct
3 Correct 204 ms 256488 KB Output is correct
4 Correct 231 ms 256408 KB Output is correct
5 Correct 209 ms 256520 KB Output is correct
6 Correct 230 ms 256416 KB Output is correct
7 Correct 231 ms 256512 KB Output is correct
8 Correct 217 ms 256540 KB Output is correct
9 Correct 212 ms 256444 KB Output is correct
10 Correct 190 ms 256408 KB Output is correct
11 Correct 240 ms 259508 KB Output is correct
12 Correct 443 ms 259480 KB Output is correct
13 Correct 284 ms 259480 KB Output is correct
14 Correct 208 ms 259404 KB Output is correct
15 Correct 211 ms 259424 KB Output is correct
16 Correct 208 ms 259348 KB Output is correct
17 Correct 219 ms 259504 KB Output is correct
18 Correct 208 ms 259444 KB Output is correct
19 Correct 219 ms 259436 KB Output is correct
20 Correct 217 ms 259440 KB Output is correct
21 Correct 210 ms 259424 KB Output is correct
22 Correct 220 ms 259384 KB Output is correct
23 Correct 386 ms 259596 KB Output is correct
24 Correct 215 ms 259308 KB Output is correct
25 Correct 350 ms 259316 KB Output is correct
26 Correct 244 ms 259360 KB Output is correct
27 Correct 206 ms 259440 KB Output is correct
28 Correct 226 ms 259432 KB Output is correct
29 Correct 222 ms 259324 KB Output is correct
30 Correct 345 ms 259324 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2620 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 256556 KB Output is correct
2 Correct 216 ms 256416 KB Output is correct
3 Correct 204 ms 256488 KB Output is correct
4 Correct 231 ms 256408 KB Output is correct
5 Correct 209 ms 256520 KB Output is correct
6 Correct 230 ms 256416 KB Output is correct
7 Correct 231 ms 256512 KB Output is correct
8 Correct 217 ms 256540 KB Output is correct
9 Correct 212 ms 256444 KB Output is correct
10 Correct 190 ms 256408 KB Output is correct
11 Correct 240 ms 259508 KB Output is correct
12 Correct 443 ms 259480 KB Output is correct
13 Correct 284 ms 259480 KB Output is correct
14 Correct 208 ms 259404 KB Output is correct
15 Correct 211 ms 259424 KB Output is correct
16 Correct 208 ms 259348 KB Output is correct
17 Correct 219 ms 259504 KB Output is correct
18 Correct 208 ms 259444 KB Output is correct
19 Correct 219 ms 259436 KB Output is correct
20 Correct 217 ms 259440 KB Output is correct
21 Correct 210 ms 259424 KB Output is correct
22 Correct 220 ms 259384 KB Output is correct
23 Correct 386 ms 259596 KB Output is correct
24 Correct 215 ms 259308 KB Output is correct
25 Correct 350 ms 259316 KB Output is correct
26 Correct 244 ms 259360 KB Output is correct
27 Correct 206 ms 259440 KB Output is correct
28 Correct 226 ms 259432 KB Output is correct
29 Correct 222 ms 259324 KB Output is correct
30 Correct 345 ms 259324 KB Output is correct
31 Runtime error 2620 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -