oj.uz

Submission #612616

# Submission time Handle Problem Language Result Execution time Memory
612616 2022-07-29T18:20:10 Z alireza_kaviani Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 484076 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++){
        int lca = vec[i][0];
        for(int j = 1 ; j < SZ(vec[i]) ; j++){
            lca = LCA(lca , vec[i][j]);
        }
        for(int j : vec[i]){
            add(LOG * MAXN + i , j , H[j] - 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 705 ms 457648 KB Output is correct
2 Correct 691 ms 457428 KB Output is correct
3 Correct 691 ms 457548 KB Output is correct
4 Correct 685 ms 457532 KB Output is correct
5 Correct 694 ms 457668 KB Output is correct
6 Correct 693 ms 457652 KB Output is correct
7 Correct 665 ms 457536 KB Output is correct
8 Correct 730 ms 457656 KB Output is correct
9 Correct 731 ms 457464 KB Output is correct
10 Correct 676 ms 457464 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 457648 KB Output is correct
2 Correct 691 ms 457428 KB Output is correct
3 Correct 691 ms 457548 KB Output is correct
4 Correct 685 ms 457532 KB Output is correct
5 Correct 694 ms 457668 KB Output is correct
6 Correct 693 ms 457652 KB Output is correct
7 Correct 665 ms 457536 KB Output is correct
8 Correct 730 ms 457656 KB Output is correct
9 Correct 731 ms 457464 KB Output is correct
10 Correct 676 ms 457464 KB Output is correct
11 Correct 718 ms 457800 KB Output is correct
12 Correct 658 ms 457720 KB Output is correct
13 Correct 713 ms 457804 KB Output is correct
14 Correct 687 ms 457736 KB Output is correct
15 Correct 740 ms 457724 KB Output is correct
16 Correct 702 ms 457796 KB Output is correct
17 Correct 848 ms 457848 KB Output is correct
18 Correct 707 ms 457824 KB Output is correct
19 Correct 756 ms 457788 KB Output is correct
20 Correct 690 ms 457800 KB Output is correct
21 Correct 784 ms 457892 KB Output is correct
22 Correct 706 ms 457712 KB Output is correct
23 Correct 697 ms 457840 KB Output is correct
24 Correct 705 ms 457776 KB Output is correct
25 Correct 673 ms 457780 KB Output is correct
26 Correct 760 ms 457800 KB Output is correct
27 Correct 721 ms 457700 KB Output is correct
28 Correct 727 ms 457744 KB Output is correct
29 Correct 712 ms 457768 KB Output is correct
30 Correct 734 ms 457708 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 457648 KB Output is correct
2 Correct 691 ms 457428 KB Output is correct
3 Correct 691 ms 457548 KB Output is correct
4 Correct 685 ms 457532 KB Output is correct
5 Correct 694 ms 457668 KB Output is correct
6 Correct 693 ms 457652 KB Output is correct
7 Correct 665 ms 457536 KB Output is correct
8 Correct 730 ms 457656 KB Output is correct
9 Correct 731 ms 457464 KB Output is correct
10 Correct 676 ms 457464 KB Output is correct
11 Correct 718 ms 457800 KB Output is correct
12 Correct 658 ms 457720 KB Output is correct
13 Correct 713 ms 457804 KB Output is correct
14 Correct 687 ms 457736 KB Output is correct
15 Correct 740 ms 457724 KB Output is correct
16 Correct 702 ms 457796 KB Output is correct
17 Correct 848 ms 457848 KB Output is correct
18 Correct 707 ms 457824 KB Output is correct
19 Correct 756 ms 457788 KB Output is correct
20 Correct 690 ms 457800 KB Output is correct
21 Correct 784 ms 457892 KB Output is correct
22 Correct 706 ms 457712 KB Output is correct
23 Correct 697 ms 457840 KB Output is correct
24 Correct 705 ms 457776 KB Output is correct
25 Correct 673 ms 457780 KB Output is correct
26 Correct 760 ms 457800 KB Output is correct
27 Correct 721 ms 457700 KB Output is correct
28 Correct 727 ms 457744 KB Output is correct
29 Correct 712 ms 457768 KB Output is correct
30 Correct 734 ms 457708 KB Output is correct
31 Execution timed out 3089 ms 484076 KB Time limit exceeded
32 Halted 0 ms 0 KB -