Submission #706077

#	Time	Username	Problem	Language	Result	Execution time	Memory
706077		pakhomovee	Capital City (JOI20_capital_city)	C++17	100 / 100	2760 ms	383476 KiB

capital_city

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <stdlib.h>
#include <map>
#include <random>
#include <cstring>
#include <functional>
#include <iomanip>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <array>
 
using namespace std;
 
const int inf = 1e9;
const int maxn = 200000;
 
int par[maxn];
int tin[maxn];
int tout[maxn];
int up[20][maxn];
int upp[20][maxn];
int d[maxn];
vector<int> gp[maxn * 21];
int timer = 0;
vector<int> c;
int id = maxn;
void dfs(int v, vector<vector<int>> &g, int p) {
    tin[v] = timer++;
    up[0][v] = p;
    gp[id].push_back(c[v]);
    upp[0][v] = id++;
    for (int i = 1; i < 20; ++i) {
        up[i][v] = up[i - 1][up[i - 1][v]];
        gp[id].push_back(upp[i - 1][up[i - 1][v]]);
        gp[id].push_back(upp[i - 1][v]);
        upp[i][v] = id++;
    }
    for (int u : g[v]) {
        if (u != p) {
            par[u] = v;
            d[u] = d[v] + 1;
            dfs(u, g, v);
        }
    }
    tout[v] = timer++;
}
 
void dfsrev(int v, vector<vector<int>> &g, int p) {
    gp[c[v]].push_back(id);
    upp[0][v] = id++;
    for (int i = 1; i < 20; ++i) {
        gp[upp[i - 1][up[i - 1][v]]].push_back(id);
        gp[upp[i - 1][v]].push_back(id);
        upp[i][v] = id++;
    }
    for (int u : g[v]) {
        if (u != p) {
            dfsrev(u, g, v);
        }
    }
}
 
bool isa(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
 
int lca(int u, int v) {
    if (isa(u, v)) return u;
    if (isa(v, u)) return v;
    for (int i = 19; i >= 0; --i) {
        if (!isa(u, v)) {
            u = up[i][u];
        }
    }
    return up[0][u];
}
 
vector<int> ord;
 
void dfs(int v, vector<int> *g, vector<bool> &used) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) {
            dfs(u, g, used);
        }
    }
    ord.push_back(v);
}
 
void dfs(int v, vector<int> *g, vector<int> &color, int cur) {
    color[v] = cur;
    for (int u : g[v]) {
        if (!color[u]) {
            dfs(u, g, color, cur);
        }
    }
}
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    fill(par, par + maxn, -1);
    c.resize(n);
    for (int& i : c) cin >> i;
    for (int& i : c) --i;
    dfs(0, g, 0);
    vector<vector<int>> groups(k);
    for (int i = 0; i < n; ++i) {
        groups[c[i]].push_back(i);
    }
    auto add_edges = [&] (int vertex, int v, int k) {
        ++k;
        for (int i = 19; i >= 0; --i) {
            if (k >= (1 << i)) {
                gp[vertex].push_back(upp[i][v]);
                v = up[i][v];
                k -= (1 << i);
            }
        }
    };
    for (vector<int> g : groups) {
        vector<pair<int, int>> x;
        for (int i : g) {
            x.push_back({ tin[i], i });
        }
        sort(x.begin(), x.end());
        vector<pair<int, int>> y = x;
        for (int i = 0; i + 1 < x.size(); ++i) {
            y.push_back({ tin[lca(x[i].second, x[i + 1].second)], lca(x[i].second, x[i + 1].second) });
        }
        sort(y.begin(), y.end());
        vector<int> st;
        for (auto [x, v] : y) {
            while (!st.empty() && !isa(st.back(), v)) st.pop_back();
            if (!st.empty()) {
                int k = d[v] - d[st.back()];
                add_edges(c[v], v, k);
            }
            st.push_back(v);
        }
    }
    vector<bool> used(id, false);
    for (int i = 0; i < id; ++i) {
        if (!used[i]) dfs(i, gp, used);
    }
    reverse(ord.begin(), ord.end());
    vector<int> color(id, 0);
    for (int i = 0; i < id; ++i) {
        gp[i].clear();
    }
    id = maxn;
    dfsrev(0, g, 0);
    auto add_rev_edges = [&] (int vertex, int v, int k) {
        ++k;
        for (int i = 19; i >= 0; --i) {
            if (k >= (1 << i)) {
                gp[upp[i][v]].push_back(vertex);
                v = up[i][v];
                k -= (1 << i);
            }
        }
    };
    for (vector<int> g : groups) {
        vector<pair<int, int>> x;
        for (int i : g) {
            x.push_back({ tin[i], i });
        }
        sort(x.begin(), x.end());
        vector<pair<int, int>> y = x;
        for (int i = 0; i + 1 < x.size(); ++i) {
            y.push_back({ tin[lca(x[i].second, x[i + 1].second)], lca(x[i].second, x[i + 1].second) });
        }
        sort(y.begin(), y.end());
        vector<int> st;
        for (auto [x, v] : y) {
            while (!st.empty() && !isa(st.back(), v)) st.pop_back();
            if (!st.empty()) {
                int k = d[v] - d[st.back()];
                add_rev_edges(c[v], v, k);
            }
            st.push_back(v);
        }
    }
    int cur = 1;
    for (int i : ord) {
        if (!color[i]) {
            dfs(i, gp, color, cur++);
        }
    }
    vector<int> sz(k, 1);
    sz.resize(id);
    vector<int> sum(id, 0);
    for (int i = 0; i < k; ++i) {
        sum[color[i] - 1] += sz[i];
    }
    int res = inf;
    --cur;
    vector<bool> ok(cur, true);
    for (int i = 0; i < id; ++i) {
        for (int j : gp[i]) {
            if (color[j] != color[i]) {
                ok[color[j] - 1] = false;
            }
        }
    }
    for (int i = 0; i < cur; ++i) {
        if (ok[i] && sum[i]) {
            res = min(res, sum[i]);
        }
    }
    cout << res - 1;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--) {
        solve();
    }
}
/*
 12 4
 7 9
 1 3
 4 6
 2 4
 10 12
 1 2
 2 10
 11 1
 2 8
 5 3
 6 7
 3
 1 1 2 4 3 3 2 2 3 4 4
 
 6 3
 2 1
 3 5
 6 2
 3 4
 2 3
 1
 3 1 2 3 2
 */

Compilation message (stderr)

capital_city.cpp: In function 'void solve()':
capital_city.cpp:142:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for (int i = 0; i + 1 < x.size(); ++i) {
      |                         ~~~~~~^~~~~~~~~~
capital_city.cpp:184:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |         for (int i = 0; i + 1 < x.size(); ++i) {
      |                         ~~~~~~^~~~~~~~~~

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