oj.uz

Submission #612592

# Submission time Handle Problem Language Result Execution time Memory
612592 2022-07-29T17:59:46 Z alireza_kaviani Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 485564 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 = 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 733 ms 457592 KB Output is correct
2 Correct 692 ms 457684 KB Output is correct
3 Correct 727 ms 457860 KB Output is correct
4 Correct 715 ms 457632 KB Output is correct
5 Correct 733 ms 457616 KB Output is correct
6 Correct 678 ms 457664 KB Output is correct
7 Correct 692 ms 457896 KB Output is correct
8 Correct 705 ms 457604 KB Output is correct
9 Correct 714 ms 457680 KB Output is correct
10 Correct 739 ms 457608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 457592 KB Output is correct
2 Correct 692 ms 457684 KB Output is correct
3 Correct 727 ms 457860 KB Output is correct
4 Correct 715 ms 457632 KB Output is correct
5 Correct 733 ms 457616 KB Output is correct
6 Correct 678 ms 457664 KB Output is correct
7 Correct 692 ms 457896 KB Output is correct
8 Correct 705 ms 457604 KB Output is correct
9 Correct 714 ms 457680 KB Output is correct
10 Correct 739 ms 457608 KB Output is correct
11 Correct 795 ms 458020 KB Output is correct
12 Correct 790 ms 457900 KB Output is correct
13 Correct 698 ms 457940 KB Output is correct
14 Correct 789 ms 457984 KB Output is correct
15 Correct 687 ms 458032 KB Output is correct
16 Correct 701 ms 458112 KB Output is correct
17 Correct 716 ms 458040 KB Output is correct
18 Correct 744 ms 457964 KB Output is correct
19 Correct 767 ms 458040 KB Output is correct
20 Correct 788 ms 457952 KB Output is correct
21 Correct 829 ms 457900 KB Output is correct
22 Correct 869 ms 458176 KB Output is correct
23 Correct 929 ms 457924 KB Output is correct
24 Correct 1027 ms 457916 KB Output is correct
25 Correct 832 ms 457896 KB Output is correct
26 Correct 822 ms 457888 KB Output is correct
27 Correct 851 ms 457944 KB Output is correct
28 Correct 829 ms 457868 KB Output is correct
29 Correct 797 ms 457904 KB Output is correct
30 Correct 834 ms 457940 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 457592 KB Output is correct
2 Correct 692 ms 457684 KB Output is correct
3 Correct 727 ms 457860 KB Output is correct
4 Correct 715 ms 457632 KB Output is correct
5 Correct 733 ms 457616 KB Output is correct
6 Correct 678 ms 457664 KB Output is correct
7 Correct 692 ms 457896 KB Output is correct
8 Correct 705 ms 457604 KB Output is correct
9 Correct 714 ms 457680 KB Output is correct
10 Correct 739 ms 457608 KB Output is correct
11 Correct 795 ms 458020 KB Output is correct
12 Correct 790 ms 457900 KB Output is correct
13 Correct 698 ms 457940 KB Output is correct
14 Correct 789 ms 457984 KB Output is correct
15 Correct 687 ms 458032 KB Output is correct
16 Correct 701 ms 458112 KB Output is correct
17 Correct 716 ms 458040 KB Output is correct
18 Correct 744 ms 457964 KB Output is correct
19 Correct 767 ms 458040 KB Output is correct
20 Correct 788 ms 457952 KB Output is correct
21 Correct 829 ms 457900 KB Output is correct
22 Correct 869 ms 458176 KB Output is correct
23 Correct 929 ms 457924 KB Output is correct
24 Correct 1027 ms 457916 KB Output is correct
25 Correct 832 ms 457896 KB Output is correct
26 Correct 822 ms 457888 KB Output is correct
27 Correct 851 ms 457944 KB Output is correct
28 Correct 829 ms 457868 KB Output is correct
29 Correct 797 ms 457904 KB Output is correct
30 Correct 834 ms 457940 KB Output is correct
31 Execution timed out 3058 ms 485564 KB Time limit exceeded
32 Halted 0 ms 0 KB -