Submission #1094280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094280		thangdz2k7	Capital City (JOI20_capital_city)	C++17	100 / 100	1453 ms	437692 KiB

capital_city

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

struct LCA{
    vi t_in, t_out, _lg, high;
    vector <vi> euler, adj;
    int cnt = 0, n, root;

    #define rz resize

    void rz(int _n, int _root){
        n = _n, root = _root;
        t_in.rz(n + 1), t_out.rz(n + 1);
        euler.rz(3 * n + 1), _lg.rz(3 * n + 1);
        adj.rz(n + 3), high.rz(n + 3, 1);
        for (int i = 1; i <= 3 * n; ++ i) _lg[i] = log2(i);
    }

    void add(int u, int v){adj[u].pb(v); adj[v].pb(u);}

    void dfs(int u, int p = 0){
        t_in[u] = ++ cnt; euler[cnt].pb(u);
        for (int v : adj[u]) if(v ^ p) {
            high[v] = high[u] + 1;
            dfs(v, u); euler[++ cnt].pb(u);
        }
        t_out[u] = cnt;
    }

    int check(int u, int v) {return t_in[u] <= t_in[v] && t_out[v] <= t_out[u];}

    int min_by_time(int u, int v) {return (t_in[u] < t_in[v] ? u : v);}

    void init(){
        dfs(root);
        for (int lg = 1; lg < LG; ++lg) {
            for (int i = 1; i + (1 << lg) - 1 <= cnt; ++i)
                euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
        }
    }

    int get(int u, int v) {
        int L = min(t_in[u], t_in[v]);
        int R = max(t_out[u], t_out[v]);
        int lg = _lg[R - L + 1];
        return min_by_time(euler[L][lg], euler[R - (1 << lg) + 1][lg]);
    }

    int dist(int u, int v){
        int lc = get(u, v);
        return high[u] + high[v] - 2 * high[lc];
    }
} pqh;

int n, k, last[N], par[N];
vi badj[N], nadj[N * LG];
int to[N][LG], idx[N][LG], nvex;

void dfs(int u = 1, int p = 0){
    par[u] = p;
    to[u][0] = u, idx[u][0] = ++ nvex;
    //cout << u << ' ' << 0 << ' ' << nvex << endl;
    for (int j = 1; j < LG; ++ j){
        int nxt = par[to[u][j - 1]];
        if (!nxt || !idx[nxt][j - 1]) break;
        to[u][j] = to[nxt][j - 1], idx[u][j] = ++ nvex;
        //cout << u << ' ' << j << ' ' << nvex << endl;
        nadj[nvex].pb(idx[u][j - 1]); nadj[nvex].pb(idx[nxt][j - 1]);
    }

    for (int v : badj[u]) if (v ^ p) dfs(v, u);
}

void add(int c, int u, int p){
    for (int l = LG - 1; l >= 0; -- l){
        int t = to[u][l]; if (!t || (par[p] && pqh.check(t, par[p]))) continue;
        //if (c == 2) cout << idx[u][l] << endl;
        nadj[c].pb(idx[u][l]); u = par[t];
    }
}

int num[N * LG], low[N * LG], ti = 0, sz[N * LG], ncom = 0, lab[N * LG];
vector <int> stk;

void vis(int u){
    num[u] = low[u] = ++ ti;
    stk.pb(u);
    for (int v : nadj[u]){
        if (num[v]) minl(low[u], num[v]);
        else vis(v), minl(low[u], low[v]);
    }

    if (low[u] == num[u]){
        ++ ncom; int v;
        do {
            v = stk.back(); stk.pop_back();
            low[v] = num[v] = 1e9;
            sz[ncom] += (v <= k);
            lab[v] = ncom;

        } while (v ^ u);
    }
}

void solve(){
    cin >> n >> k; pqh.rz(n, 1); nvex = k;
    for (int i = 1, u, v; i < n; ++ i){
        cin >> u >> v;
        badj[u].pb(v); badj[v].pb(u);
        pqh.add(u, v);
    }
    pqh.init(); dfs();
    for (int i = 1; i <= n; ++ i){
        int c; cin >> c;
        nadj[idx[i][0]].pb(c);
        if (last[c]) {
            int p = pqh.get(i, last[c]);;
            add(c, i, p); add(c, last[c], p);
        }
        last[c] = i;
    }
    for (int i = 1; i <= nvex; ++ i) if (!num[i]) vis(i);
    int ans = k; //cout << lab[1] << ' ' << lab[2] << ' ' << lab[3] << endl;
    vector <bool> ck(ncom + 1, true);
    for (int i = 1; i <= nvex; ++ i){
        for (int j : nadj[i]) {
            //cout << i << ' ' << j << endl;
            if (lab[i] ^ lab[j]) ck[lab[i]] = false;
        }
    }
    for (int i = 1; i <= ncom; ++ i) if (ck[i]) {
        minl(ans, sz[i]); //cout << i << ' ' << sz[i] << endl;
    }
    cout << ans - 1;
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

capital_city.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
capital_city.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
capital_city.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
capital_city.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
capital_city.cpp: In member function 'void LCA::init()':
capital_city.cpp:56:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |                 euler[i].pb(min_by_time(euler[i][lg - 1], euler[i + (1 << lg - 1)][lg - 1]));
      |                                                                           ~~~^~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59