oj.uz

Submission #612611

# Submission time Handle Problem Language Result Execution time Memory
612611 2022-07-29T18:15:44 Z alireza_kaviani Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 483960 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 , ptr , ans = MOD , C[MAXN] , par[LOG][MAXN] , H[MAXN] , mark[MAX] , ord[MAX];
vector<int> tree[MAXN] , adj[MAX] , radj[MAX] , vec[MAXN];

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[ptr++] = 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(ord , ord + MAX);
    for(int i = 0 ; i < MAX ; i++){
        if(mark[ord[i]])    continue;
        cnt = 0;
        DFS2(ord[i]);
        DFS3(ord[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 = 0 ; j < MAXN ; 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 668 ms 457548 KB Output is correct
2 Correct 666 ms 457508 KB Output is correct
3 Correct 675 ms 457476 KB Output is correct
4 Correct 706 ms 457548 KB Output is correct
5 Correct 665 ms 457476 KB Output is correct
6 Correct 667 ms 457472 KB Output is correct
7 Correct 716 ms 457552 KB Output is correct
8 Correct 688 ms 457460 KB Output is correct
9 Correct 696 ms 457648 KB Output is correct
10 Correct 671 ms 457436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 457548 KB Output is correct
2 Correct 666 ms 457508 KB Output is correct
3 Correct 675 ms 457476 KB Output is correct
4 Correct 706 ms 457548 KB Output is correct
5 Correct 665 ms 457476 KB Output is correct
6 Correct 667 ms 457472 KB Output is correct
7 Correct 716 ms 457552 KB Output is correct
8 Correct 688 ms 457460 KB Output is correct
9 Correct 696 ms 457648 KB Output is correct
10 Correct 671 ms 457436 KB Output is correct
11 Correct 758 ms 457792 KB Output is correct
12 Correct 708 ms 457784 KB Output is correct
13 Correct 703 ms 457768 KB Output is correct
14 Correct 726 ms 457976 KB Output is correct
15 Correct 681 ms 457764 KB Output is correct
16 Correct 697 ms 457932 KB Output is correct
17 Correct 719 ms 457752 KB Output is correct
18 Correct 670 ms 457800 KB Output is correct
19 Correct 759 ms 457816 KB Output is correct
20 Correct 716 ms 457696 KB Output is correct
21 Correct 737 ms 457916 KB Output is correct
22 Correct 695 ms 457748 KB Output is correct
23 Correct 668 ms 457852 KB Output is correct
24 Correct 716 ms 457720 KB Output is correct
25 Correct 694 ms 457728 KB Output is correct
26 Correct 673 ms 457956 KB Output is correct
27 Correct 702 ms 457744 KB Output is correct
28 Correct 689 ms 457816 KB Output is correct
29 Correct 678 ms 457812 KB Output is correct
30 Correct 682 ms 457792 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 483960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 457548 KB Output is correct
2 Correct 666 ms 457508 KB Output is correct
3 Correct 675 ms 457476 KB Output is correct
4 Correct 706 ms 457548 KB Output is correct
5 Correct 665 ms 457476 KB Output is correct
6 Correct 667 ms 457472 KB Output is correct
7 Correct 716 ms 457552 KB Output is correct
8 Correct 688 ms 457460 KB Output is correct
9 Correct 696 ms 457648 KB Output is correct
10 Correct 671 ms 457436 KB Output is correct
11 Correct 758 ms 457792 KB Output is correct
12 Correct 708 ms 457784 KB Output is correct
13 Correct 703 ms 457768 KB Output is correct
14 Correct 726 ms 457976 KB Output is correct
15 Correct 681 ms 457764 KB Output is correct
16 Correct 697 ms 457932 KB Output is correct
17 Correct 719 ms 457752 KB Output is correct
18 Correct 670 ms 457800 KB Output is correct
19 Correct 759 ms 457816 KB Output is correct
20 Correct 716 ms 457696 KB Output is correct
21 Correct 737 ms 457916 KB Output is correct
22 Correct 695 ms 457748 KB Output is correct
23 Correct 668 ms 457852 KB Output is correct
24 Correct 716 ms 457720 KB Output is correct
25 Correct 694 ms 457728 KB Output is correct
26 Correct 673 ms 457956 KB Output is correct
27 Correct 702 ms 457744 KB Output is correct
28 Correct 689 ms 457816 KB Output is correct
29 Correct 678 ms 457812 KB Output is correct
30 Correct 682 ms 457792 KB Output is correct
31 Execution timed out 3070 ms 483960 KB Time limit exceeded
32 Halted 0 ms 0 KB -