Submission #938182

#	Time	Username	Problem	Language	Result	Execution time	Memory
938182		Pring	Capital City (JOI20_capital_city)	C++17	0 / 100	2810 ms	494332 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_bin(int x, int w, int c) {
        GRAPH::ADD_EDGE(c, lf[x][w]);
        return p[x][w];
    }

    int leap(int x, int k, int c) {
        for (int w = __lg(n); w >= 0; w--) {
            if (k & w) x = leap_bin(x, w, c);
        }
        return x;
    }

    int lca(int x, int y, int c) {
        if (d[x] < d[y]) swap(x, y);
        x = leap(x, d[x] - d[y], c);
        if (x == y) return x;
        for (int w = __lg(n); w >= 0; w--) {
            if (p[x][w] == p[y][w]) continue;
            x = leap_bin(x, w, c);
            y = leap_bin(y, w, c);
        }
        leap_bin(x, 0, c);
        leap_bin(y, 0, c);
        return p[x][0];
    }

    void BUILD(vector<int> v, int c) {
        debug(c);
        // for (auto &i : v) cout << i << ' ';
        // cout << endl;
        if (v.size() == 1) {
            GRAPH::ADD_EDGE(c, lf[v[0]][0]);
            return;
        }
        int lca_now = v.back();
        GRAPH::ADD_EDGE(c, lf[lca_now][0]);
        v.pop_back();
        for (auto &i : v) {
            lca_now = lca(lca_now, i, c);
            GRAPH::ADD_EDGE(c, lf[lca_now][0]);
        }
    }
}

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);
      |             ^~~~~
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
capital_city.cpp:113:17: note: in expansion of macro 'debug'
  113 |                 debug(i, p[p[i][w - 1]][w - 1]);
      |                 ^~~~~
capital_city.cpp: In function 'void TREE::BUILD(std::vector<int>, int)':
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
capital_city.cpp:146:9: note: in expansion of macro 'debug'
  146 |         debug(c);
      |         ^~~~~

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