Submission #1142861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142861		Persia	Capital City (JOI20_capital_city)	C++17	11 / 100	3115 ms	428528 KiB

capital_city

#include <bits/stdc++.h>
#define bit(i, x) (x >> i & 1)
#define ll long long
const int N = 2e5 + 5;
const int mod = 998244353;
using namespace std;

int n, k;
vector<int> G[N];
int c[N];

// additional
vector<int> b[N];
vector<int> G2[N];

// lca
int f[N][19], h[N];

// scc
int num[N], low[N], cnt;
int col[N], ct;
vector<int> stk;
int deg[N], num2[N];

// result
int res = 1e9;

void predfs(int u = 1, int par = -1) {
    for(int i = 1; i <= 17; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(int v : G[u]) if(v != par) {
        f[v][0] = u;
        h[v] = h[u] + 1;
        predfs(v, u);
    }
}

int lca(int x, int y) {
    if(h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for(int i = 0; i <= 17; i++) if(bit(i, d)) x = f[x][i];
    if(x == y) return x;
    for(int i = 17; i >= 0; i--) if(f[x][i] != f[y][i]) {
        x = f[x][i];
        y = f[y][i];
    }
    return f[x][0];
}

void addedge(int x, int y) {
    if(x == y) return;
    G2[x].push_back(y);

    // if(x == 4) cerr << y << " ";
    // cerr << x << " " << y << "\n";
} 

void goup(int x, int u, int p) {
    while(1) {
        addedge(x, c[u]);

        // if(x == 4) cerr << u << " ";

        if(u == p) break;
        u = f[u][0];
    }
}

void dfs(int u) {
    // cerr << u << " ";
    num[u] = low[u] = ++cnt;
    stk.push_back(u);
    for(int v : G2[u]) if(!col[v]) {
        if(num[v]) low[u] = min(low[u], num[v]);
        else {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if(num[u] == low[u]) {
        ct++;
        // cerr << ct << ": ";
        while(1) {
            int top = stk.back();
            stk.pop_back();
            num2[ct]++;
            col[top] = ct;

            // cerr << top << " ";

            if(top == u) break;
        }
        // cerr << "\n";
    }
}

signed main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // Xay dung do thi co huong giua k mau voi nhau, ton tai canh (i -> j) neu tplt nho nhat chua tat ca dinh mau i co chua it nhat mot dinh nhau j. Bai toan tro thanh tim tplt manh tren do thi co huong ma co so dinh la nho nhat.

    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) cin >> c[i];

    for(int i = 1; i <= n; i++) {
        b[c[i]].push_back(i);
        assert(c[i] >= 1 && c[i] <= k);
    }
    predfs();
    for(int i = 1; i <= k; i++) if(!b[i].empty()) {
        int u = b[i][0];
        for(int j : b[i]) u = lca(u, j);
        for(int j : b[i]) goup(i, j, u);
    }
    for(int i = 1; i <= k; i++) if(!num[i]) {
        dfs(i);
        // cerr << "\n";
    }
    for(int i = 1; i <= k; i++) {
        for(int j : G2[i]) if(col[i] != col[j]) {
            deg[col[i]]++;
        }
    }
    for(int i = 1; i <= ct; i++) {
        // cout << deg[i] << " " << num2[i] << "\n";
        if(!deg[i]) res = min(res, num2[i]);
    }
    cout << res - 1;

    // Debug

    // for(int i : G2[4]) cout << i << " ";

    // for(int i = 1; i <= k; i++) cerr << i << " " << low[i] << "\n";
    
    // for(int i = 1; i <= k; i++) {
    //     for(int j : b[i]) cout << j << " ";
    //     cout << "\n";
    // }

    return 0 ^ 0;
}

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