oj.uz

Submission #706064

# Submission time Handle Problem Language Result Execution time Memory
706064 2023-03-05T19:50:59 Z pakhomovee Capital City (JOI20_capital_city) C++17
11 / 100
 1351 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 = 1 << 18;

int par[maxn];
int tin[maxn];
int tout[maxn];
int up[20][maxn];
int upp[20][maxn];
int d[maxn];
vector<int> gp[maxn * 20];
vector<int> rgp[maxn * 20];
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

# Verdict Execution time Memory Grader output
1 Correct 117 ms 251964 KB Output is correct
2 Correct 125 ms 251964 KB Output is correct
3 Correct 117 ms 251972 KB Output is correct
4 Correct 115 ms 252156 KB Output is correct
5 Correct 119 ms 252020 KB Output is correct
6 Correct 116 ms 252000 KB Output is correct
7 Correct 116 ms 251964 KB Output is correct
8 Correct 116 ms 252016 KB Output is correct
9 Correct 116 ms 251984 KB Output is correct
10 Correct 121 ms 251936 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 251964 KB Output is correct
2 Correct 125 ms 251964 KB Output is correct
3 Correct 117 ms 251972 KB Output is correct
4 Correct 115 ms 252156 KB Output is correct
5 Correct 119 ms 252020 KB Output is correct
6 Correct 116 ms 252000 KB Output is correct
7 Correct 116 ms 251964 KB Output is correct
8 Correct 116 ms 252016 KB Output is correct
9 Correct 116 ms 251984 KB Output is correct
10 Correct 121 ms 251936 KB Output is correct
11 Correct 138 ms 255884 KB Output is correct
12 Correct 128 ms 255908 KB Output is correct
13 Correct 127 ms 255896 KB Output is correct
14 Correct 126 ms 255844 KB Output is correct
15 Correct 135 ms 255900 KB Output is correct
16 Correct 127 ms 255960 KB Output is correct
17 Correct 126 ms 255912 KB Output is correct
18 Correct 130 ms 255956 KB Output is correct
19 Correct 124 ms 255976 KB Output is correct
20 Correct 133 ms 255952 KB Output is correct
21 Correct 135 ms 256124 KB Output is correct
22 Correct 129 ms 255940 KB Output is correct
23 Correct 128 ms 255916 KB Output is correct
24 Correct 146 ms 255936 KB Output is correct
25 Correct 130 ms 255848 KB Output is correct
26 Correct 128 ms 255892 KB Output is correct
27 Correct 136 ms 255876 KB Output is correct
28 Correct 138 ms 255916 KB Output is correct
29 Correct 126 ms 255932 KB Output is correct
30 Correct 137 ms 255900 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1351 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 251964 KB Output is correct
2 Correct 125 ms 251964 KB Output is correct
3 Correct 117 ms 251972 KB Output is correct
4 Correct 115 ms 252156 KB Output is correct
5 Correct 119 ms 252020 KB Output is correct
6 Correct 116 ms 252000 KB Output is correct
7 Correct 116 ms 251964 KB Output is correct
8 Correct 116 ms 252016 KB Output is correct
9 Correct 116 ms 251984 KB Output is correct
10 Correct 121 ms 251936 KB Output is correct
11 Correct 138 ms 255884 KB Output is correct
12 Correct 128 ms 255908 KB Output is correct
13 Correct 127 ms 255896 KB Output is correct
14 Correct 126 ms 255844 KB Output is correct
15 Correct 135 ms 255900 KB Output is correct
16 Correct 127 ms 255960 KB Output is correct
17 Correct 126 ms 255912 KB Output is correct
18 Correct 130 ms 255956 KB Output is correct
19 Correct 124 ms 255976 KB Output is correct
20 Correct 133 ms 255952 KB Output is correct
21 Correct 135 ms 256124 KB Output is correct
22 Correct 129 ms 255940 KB Output is correct
23 Correct 128 ms 255916 KB Output is correct
24 Correct 146 ms 255936 KB Output is correct
25 Correct 130 ms 255848 KB Output is correct
26 Correct 128 ms 255892 KB Output is correct
27 Correct 136 ms 255876 KB Output is correct
28 Correct 138 ms 255916 KB Output is correct
29 Correct 126 ms 255932 KB Output is correct
30 Correct 137 ms 255900 KB Output is correct
31 Runtime error 1351 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -