Submission #938194

#	Time	Username	Problem	Language	Result	Execution time	Memory
938194		Pring	Capital City (JOI20_capital_city)	C++17	100 / 100	2947 ms	480840 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005;
int n, k;
vector<int> clr[MXN];

namespace GRAPH {
    int nc;
    vector<int> edge[MXN * 20];
    int dfn[MXN * 20], low[MXN * 20], scc[MXN * 20], ns, C;
    vector<int> st;
    int out[MXN * 20];

    void ADD_EDGE(int x, int y) {
        edge[x].push_back(y);
    }

    void DFS(int id) {
        C++;
        dfn[id] = C;
        low[id] = C;
        st.push_back(id);
        for (auto &i : edge[id]) {
            if (scc[i]) continue;
            if (dfn[i]) {
                low[id] = min(low[id], dfn[i]);
            } else {
                DFS(i);
                low[id] = min(low[id], low[i]);
            }
        }
        if (dfn[id] == low[id]) {
            int x;
            ns++;
            do {
                x = st.back();
                st.pop_back();
                scc[x] = ns;
            } while (x != id);
        }
    }

    void SCC() {
        FOR(i, 1, nc + 1) {
            if (dfn[i]) continue;
            DFS(i);
        }
    }

    int GET_ANS() {
        FOR(id, 1, nc + 1) {
            for (auto &i : edge[id]) {
                if (scc[i] == scc[id]) continue;
                out[scc[id]]++;
            }
        }
        map<int, int> M;
        FOR(i, n + 1, n + k + 1) if (out[scc[i]] == 0) M[scc[i]]++;
        int ans = INT_MAX;
        for (auto i : M) ans = min(ans, i.sc);
        return ans;
    }
}

namespace TREE {
    vector<int> edge[MXN], lf[MXN];
    vector<int> p[MXN];
    int d[MXN];
    
    void ADD_EDGE(int x, int y) {
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    void DFS(int id, int par, int dep) {
        p[id].push_back(par);
        d[id] = dep;
        for (auto &i : edge[id]) {
            if (i == par) continue;
            DFS(i, id, dep + 1);
        }
    }

    void LIFT() {
        DFS(1, 1, 0);
        FOR(i, 1, n + 1) lf[i].push_back(i);
        for(int w = 1; (1 << w) <= n; w++) {
            debug(w);
            FOR(i, 1, n + 1) {
                int now = ++GRAPH::nc;
                GRAPH::ADD_EDGE(now, lf[i][w - 1]);
                GRAPH::ADD_EDGE(now, lf[p[i].back()][w - 1]);
                lf[i].push_back(now);
            }
            FOR(i, 1, n + 1) {
                // debug(i, p[p[i][w - 1]][w - 1]);
                p[i].push_back(p[p[i][w - 1]][w - 1]);
            }
        }
    }

    int leap(int x, int k, int c) {
        for (int w = p[1].size() - 1; w >= 0; w--) if (k & (1 << w)) {
            if (c != -1) GRAPH::ADD_EDGE(c, lf[x][w]);
            x = p[x][w];
        }
        return x;
    }

    int lca(int x, int y) {
        if (d[x] < d[y]) swap(x, y);
        x = leap(x, d[x] - d[y], -1);
        if (x == y) return x;
        for (int w = p[1].size() - 1; w >= 0; w--) {
            if (p[x][w] == p[y][w]) continue;
            x = p[x][w];
            y = p[y][w];
        }
        return p[x][0];
    }

    void BUILD(vector<int> v, int c) {
        int lca_now = v.back();
        for (auto &i : v) lca_now = lca(lca_now, i);
        for (auto &i : v) leap(i, d[i] - d[lca_now], c);
        GRAPH::ADD_EDGE(c, lca_now);
    }
}

void miku() {
    int a, b;
    cin >> n >> k;
    GRAPH::nc = n + k;
    FOR(i, 1, n) {
        cin >> a >> b;
        TREE::ADD_EDGE(a, b);
    }
    FOR(i, 1, n + 1) {
        cin >> a;
        clr[a].push_back(i);
        GRAPH::ADD_EDGE(i, a + n);
    }
    TREE::LIFT();
    FOR(i, 1, k + 1) {
        TREE::BUILD(clr[i], i + n);
    }
    GRAPH::SCC();
    cout << GRAPH::GET_ANS() - 1 << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void TREE::LIFT()':
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
capital_city.cpp:105:13: note: in expansion of macro 'debug'
  105 |             debug(w);
      |             ^~~~~

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