oj.uz

답안 #706068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706068 2023-03-05T19:56:55 Z pakhomovee 수도 (JOI20_capital_city) C++17
11 / 100
 1908 ms 524288 KB 
#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];
vector<int> rgp[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]);
    rgp[c[v]].push_back(id);
    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]);
        rgp[upp[i - 1][v]].push_back(id);
        rgp[upp[i - 1][up[i - 1][v]]].push_back(id);
        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++;
}

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]);
                rgp[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_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);
    int cur = 1;
    for (int i : ord) {
        if (!color[i]) {
            dfs(i, rgp, 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[i] - 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

capital_city.cpp: In function 'void solve()':
capital_city.cpp:132: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]
  132 |         for (int i = 0; i + 1 < x.size(); ++i) {
      |                         ~~~~~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 201888 KB Output is correct
2 Correct 120 ms 201860 KB Output is correct
3 Correct 96 ms 201896 KB Output is correct
4 Correct 99 ms 201852 KB Output is correct
5 Correct 106 ms 201828 KB Output is correct
6 Correct 98 ms 201932 KB Output is correct
7 Correct 94 ms 201792 KB Output is correct
8 Correct 106 ms 201820 KB Output is correct
9 Correct 95 ms 201840 KB Output is correct
10 Correct 93 ms 201796 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 201888 KB Output is correct
2 Correct 120 ms 201860 KB Output is correct
3 Correct 96 ms 201896 KB Output is correct
4 Correct 99 ms 201852 KB Output is correct
5 Correct 106 ms 201828 KB Output is correct
6 Correct 98 ms 201932 KB Output is correct
7 Correct 94 ms 201792 KB Output is correct
8 Correct 106 ms 201820 KB Output is correct
9 Correct 95 ms 201840 KB Output is correct
10 Correct 93 ms 201796 KB Output is correct
11 Correct 108 ms 205632 KB Output is correct
12 Correct 105 ms 205644 KB Output is correct
13 Correct 112 ms 205648 KB Output is correct
14 Correct 103 ms 205648 KB Output is correct
15 Correct 103 ms 205712 KB Output is correct
16 Correct 113 ms 205756 KB Output is correct
17 Correct 106 ms 205648 KB Output is correct
18 Correct 105 ms 205728 KB Output is correct
19 Correct 105 ms 205760 KB Output is correct
20 Correct 108 ms 205652 KB Output is correct
21 Correct 110 ms 205772 KB Output is correct
22 Correct 115 ms 205744 KB Output is correct
23 Correct 105 ms 205732 KB Output is correct
24 Correct 106 ms 205688 KB Output is correct
25 Correct 107 ms 205668 KB Output is correct
26 Correct 107 ms 205732 KB Output is correct
27 Correct 104 ms 205632 KB Output is correct
28 Correct 109 ms 205708 KB Output is correct
29 Correct 138 ms 205624 KB Output is correct
30 Correct 110 ms 205740 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1908 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 201888 KB Output is correct
2 Correct 120 ms 201860 KB Output is correct
3 Correct 96 ms 201896 KB Output is correct
4 Correct 99 ms 201852 KB Output is correct
5 Correct 106 ms 201828 KB Output is correct
6 Correct 98 ms 201932 KB Output is correct
7 Correct 94 ms 201792 KB Output is correct
8 Correct 106 ms 201820 KB Output is correct
9 Correct 95 ms 201840 KB Output is correct
10 Correct 93 ms 201796 KB Output is correct
11 Correct 108 ms 205632 KB Output is correct
12 Correct 105 ms 205644 KB Output is correct
13 Correct 112 ms 205648 KB Output is correct
14 Correct 103 ms 205648 KB Output is correct
15 Correct 103 ms 205712 KB Output is correct
16 Correct 113 ms 205756 KB Output is correct
17 Correct 106 ms 205648 KB Output is correct
18 Correct 105 ms 205728 KB Output is correct
19 Correct 105 ms 205760 KB Output is correct
20 Correct 108 ms 205652 KB Output is correct
21 Correct 110 ms 205772 KB Output is correct
22 Correct 115 ms 205744 KB Output is correct
23 Correct 105 ms 205732 KB Output is correct
24 Correct 106 ms 205688 KB Output is correct
25 Correct 107 ms 205668 KB Output is correct
26 Correct 107 ms 205732 KB Output is correct
27 Correct 104 ms 205632 KB Output is correct
28 Correct 109 ms 205708 KB Output is correct
29 Correct 138 ms 205624 KB Output is correct
30 Correct 110 ms 205740 KB Output is correct
31 Runtime error 1908 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -