oj.uz

Submission #706067

# Submission time Handle Problem Language Result Execution time Memory
706067 2023-03-05T19:53:57 Z pakhomovee Capital City (JOI20_capital_city) C++17
11 / 100
 1139 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 * 25];
vector<int> rgp[maxn * 25];
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 145 ms 313532 KB Output is correct
2 Correct 148 ms 313580 KB Output is correct
3 Correct 147 ms 313532 KB Output is correct
4 Correct 144 ms 313532 KB Output is correct
5 Correct 149 ms 313500 KB Output is correct
6 Correct 148 ms 313580 KB Output is correct
7 Correct 147 ms 313492 KB Output is correct
8 Correct 145 ms 313532 KB Output is correct
9 Correct 144 ms 313532 KB Output is correct
10 Correct 145 ms 313540 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 313532 KB Output is correct
2 Correct 148 ms 313580 KB Output is correct
3 Correct 147 ms 313532 KB Output is correct
4 Correct 144 ms 313532 KB Output is correct
5 Correct 149 ms 313500 KB Output is correct
6 Correct 148 ms 313580 KB Output is correct
7 Correct 147 ms 313492 KB Output is correct
8 Correct 145 ms 313532 KB Output is correct
9 Correct 144 ms 313532 KB Output is correct
10 Correct 145 ms 313540 KB Output is correct
11 Correct 159 ms 317432 KB Output is correct
12 Correct 155 ms 317408 KB Output is correct
13 Correct 155 ms 317500 KB Output is correct
14 Correct 154 ms 317504 KB Output is correct
15 Correct 153 ms 317436 KB Output is correct
16 Correct 155 ms 317516 KB Output is correct
17 Correct 154 ms 317520 KB Output is correct
18 Correct 159 ms 317552 KB Output is correct
19 Correct 154 ms 317520 KB Output is correct
20 Correct 155 ms 317552 KB Output is correct
21 Correct 155 ms 317484 KB Output is correct
22 Correct 155 ms 317528 KB Output is correct
23 Correct 154 ms 317532 KB Output is correct
24 Correct 163 ms 317444 KB Output is correct
25 Correct 154 ms 317500 KB Output is correct
26 Correct 160 ms 317584 KB Output is correct
27 Correct 154 ms 317516 KB Output is correct
28 Correct 155 ms 317472 KB Output is correct
29 Correct 154 ms 317504 KB Output is correct
30 Correct 159 ms 317428 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1139 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 145 ms 313532 KB Output is correct
2 Correct 148 ms 313580 KB Output is correct
3 Correct 147 ms 313532 KB Output is correct
4 Correct 144 ms 313532 KB Output is correct
5 Correct 149 ms 313500 KB Output is correct
6 Correct 148 ms 313580 KB Output is correct
7 Correct 147 ms 313492 KB Output is correct
8 Correct 145 ms 313532 KB Output is correct
9 Correct 144 ms 313532 KB Output is correct
10 Correct 145 ms 313540 KB Output is correct
11 Correct 159 ms 317432 KB Output is correct
12 Correct 155 ms 317408 KB Output is correct
13 Correct 155 ms 317500 KB Output is correct
14 Correct 154 ms 317504 KB Output is correct
15 Correct 153 ms 317436 KB Output is correct
16 Correct 155 ms 317516 KB Output is correct
17 Correct 154 ms 317520 KB Output is correct
18 Correct 159 ms 317552 KB Output is correct
19 Correct 154 ms 317520 KB Output is correct
20 Correct 155 ms 317552 KB Output is correct
21 Correct 155 ms 317484 KB Output is correct
22 Correct 155 ms 317528 KB Output is correct
23 Correct 154 ms 317532 KB Output is correct
24 Correct 163 ms 317444 KB Output is correct
25 Correct 154 ms 317500 KB Output is correct
26 Correct 160 ms 317584 KB Output is correct
27 Correct 154 ms 317516 KB Output is correct
28 Correct 155 ms 317472 KB Output is correct
29 Correct 154 ms 317504 KB Output is correct
30 Correct 159 ms 317428 KB Output is correct
31 Runtime error 1139 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -