Submission #1279999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279999		phuocrucpp	수도 (JOI20_capital_city)	C++20	11 / 100	3104 ms	161872 KiB

capital_city

/*ㅤ∧＿∧
　(　･∀･)
　(　つ┳⊃
ε (_)へ⌒ヽﾌ
 (　　(　･ω･)
 ◎―◎   ⊃  ⊃
BePhuongSuperSuwi
From TK4 - CHT
ㅤㅤ／ ⌒＼____
　 /・　　 ）　　\
　/ノへ ノ　　　 /|
ノ　　  ＼\ |/_/_/*/


#include<bits/stdc++.h>
#define task "main"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define int long long
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii, ii>
#define base 341
#define MASK(i) (1ll << i)
#define oo 1e18
#define isOn(x,i) ((x) & MASK(i))
#define bitOn(x,i) ((x) | MASK(i))
#define bitOff(x,i) ((x) & ~MASK(i))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
using namespace std;
//using namespace __gnu_pbds;
const int maxn = 2e5 + 5;
const int lg = 18;
int n, k, val[maxn], h[maxn], par[maxn][lg + 2];
vector <int> g[maxn], c[maxn];

void dfs(int u, int p) {
    for (int x : g[u]) {
        if (x == p) continue;
        h[x] = h[u] + 1;
        par[x][0] = u;
        dfs(x, u);
    }
}
int lca(int u, int v) {
    if (h[u] < h[v]) swap(u,v);
    for (int i = lg; i >= 0; i--) {
        if ((h[u] - h[v]) >= MASK(i)) u = par[u][i];
    }
    if (u == v) return u;
    for (int i = lg; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
void prelca() {
    dfs(1, -1);
    for (int j = 1; j <= lg; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
}


namespace giai1{
    vector <int> c[maxn];
    bool ok[maxn];
    int parent[maxn];
    vector <int> cur;

    int acs(int u) {
        if (parent[u] == u) return u;
        else return parent[u] = acs(parent[u]);
    }

    void join(int u, int v) {
        int x = acs(u);
        int y = acs(v);
        if (x != y) {
            parent[x] = y;
        }
    }

    void connect(int u, int v) {
        int p = lca(u, v);
        while(h[u] > h[p]) {
            if (!ok[val[u]]) ok[val[u]] = 1, cur.pb(val[u]);
            join(u, par[u][0]);
            u = acs(u);
        }

        while(h[v] > h[p]) {
            if (!ok[val[v]]) ok[val[v]] = 1, cur.pb(val[v]);
            join(v, par[v][0]);
            v = acs(v);
        }

        if (!ok[val[p]]) ok[val[p]] = 1, cur.pb(val[p]);
    }

    int mini = oo;
    void tinh(int id) {
        for (int i = 1; i <= n; i++) parent[i] = i, ok[i] = 0;
        cur.clear();
        ok[id] = 1;
        cur.pb(id);

        for (int i = 0; i < cur.size(); i++) {
            int x = cur[i];
            for (int i = 1; i < c[x].size(); i++) {
                connect(c[x][0], c[x][i]);
            }
        }
        mini = min(mini, (int)cur.size() - 1);
    }

    void solve() {
        for (int i = 1; i <= n; i++)
                c[val[i]].pb(i);

        for (int i = 1; i <= k; i++) {
            tinh(i);
          //  break;
        }
        cout << mini;
    }
}

namespace giai2{
    vector <int> adj[maxn];
    int lim = 0;
    vector <ii> ed;
    int tin[maxn], tour[maxn], timer = 0;
    struct HLD{
        int sz[maxn], Head[maxn], Pos[maxn], Id[maxn], chain, timer = 0, h[maxn], par[maxn];
        int st[maxn * 4];

        void build(int id, int l, int r) {
            st[id] = ++lim;
            if (l == r) {
                adj[st[id]].pb(val[tour[l]]);
                ed.pb({st[id], val[tour[l]]});
              //  cout << st[id] << " " << val[tour[l]] << endl;
                return;
            }
            int m = (l + r) / 2;
            build(id * 2, l, m);
            build(id * 2 + 1, m + 1, r);
            adj[st[id]].pb(st[id * 2]);
            adj[st[id]].pb(st[id * 2 + 1]);

            ed.pb({st[id], st[id * 2]});
            ed.pb({st[id], st[id * 2 + 1]});
    //        cout << st[id] << " " << st[id * 2] << endl;
    //        cout << st[id] << " " << st[id * 2 + 1] << endl;
        }
        void dfs(int u, int p) {
            sz[u] = 1;
            for (int x : g[u]) {
                if (x == p) continue;
                h[x] = h[u] + 1;
                par[x] = u;
                dfs(x, u);
                sz[u] += sz[x];
            }
        }

        void hld(int u, int p) {
            if (!Head[chain]) {
                Head[chain] = u;
            }
            Id[u] = chain;
            Pos[u] = tin[u] = ++timer;
            tour[timer] = u;
            int nxt = 0;
            for (int x : g[u]) {
                if (x == p) continue;
                if (nxt == 0 || sz[nxt] < sz[x]) nxt = x;
            }
            if (nxt) hld(nxt, u);
            for (int x : g[u]) {
                if (x == p || x == nxt) continue;
                chain++;
                hld(x, u);
            }
        }

        void update(int id, int l, int r, int u, int v, int idx) {
            if (u > r || v < l) return;
            if (l >= u && r <= v) {
                adj[idx].pb(st[id]);
                ed.pb({idx, st[id]});
              //  cout  << idx << " " << st[id] << endl;
                return;
            }

            int m = (l + r) / 2;
            update(id * 2, l, m, u, v, idx);
            update(id * 2 + 1, m + 1, r, u, v, idx);
        }
        void upd(int u, int v, int idx) {
            while (Id[u] != Id[v]) {
                if (h[Head[Id[u]]] > h[Head[Id[v]]]) swap(u,v);
                update(1,1,n,Pos[Head[Id[v]]], Pos[v], idx);
                v = par[Head[Id[v]]];
            }
            if (h[u] > h[v]) swap(u,v);
            update(1,1,n,Pos[u], Pos[v], idx);
        }

        void init() {
            timer = 0;
            dfs(1, -1);
            chain = 1;
            hld(1, -1);

            build(1, 1, n);
        }
    } hld1;

    int d[maxn], low[maxn], ssc[maxn], tplt, sz[maxn];
    bool in[maxn];
    stack <int> stk;
    void dfs(int u) {
        d[u] = low[u] = ++timer;
        stk.push(u);
        for (int x : adj[u]) {
            if (d[x] == 0) {
                dfs(x);
                low[u] = min(low[u], low[x]);
            } else if (!in[x]) {
                low[u] = min(low[u], d[x]);
            }
        }
        if (d[u] == low[u]) {
            int p;
            tplt++;
            do{
                p = stk.top();
                in[p] = true;
                ssc[p] = tplt;
                if (p <= k)
                    sz[tplt]++;
                stk.pop();
            }while(p!=u);
        }
    }

    bool ok[maxn];

    bool ss(int x, int y) {
        return tin[x] < tin[y];
    }
    void solve() {
        for (int i = 1; i <= n; i++) c[val[i]].pb(i);
        lim = k;

        hld1.init();

      //  for (int i = 1; i <= n; i++) cout << tin[i] << endl;
     //   cout << lim << endl;
        for (int i = 1; i <= k; i++){
            sort(c[i].begin(), c[i].end(), ss);
            for (int j = 0; j < c[i].size() - 1; j++) {
                hld1.upd(c[i][j], c[i][j + 1], i);
           //     cout << i << " " << c[i][j] << " " << c[i][j + 1] << endl;
            }
        }



        timer = 0;
        for (int i = 1; i <= lim; i++) {
            if (!d[i]) dfs(i);
        }

//       // cout << tplt << endl;
        for (int u = 1; u <= lim; u++) {
            for (int v : adj[u]) {
                int l = ssc[u], r = ssc[v];
                if (l != r) {
                    ok[l] = 1;
                }
            }
        }

        int mini = oo;
        for (int i = 1; i <= tplt; i++) {
            if (!ok[i]) {
                mini = min(mini, sz[i] - 1);
                //cout << "ssc " << i << " " << sz[i] << endl;
            }
        }
        cout << mini;
    }
}


main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int l, r;
        cin >> l >> r;
        g[l].pb(r); g[r].pb(l);
    }
    prelca();
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

 //   giai2::solve();
    giai2::solve();
//    if (n <= 2000) giai1::solve();
//    else giai2::solve();
}

Compilation message (stderr)

capital_city.cpp:308:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  308 | main() {
      | ^~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:311:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  311 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:312:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  312 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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