oj.uz

Submission #706065

# Submission time Handle Problem Language Result Execution time Memory
706065 2023-03-05T19:51:44 Z pakhomovee Capital City (JOI20_capital_city) C++17
11 / 100
 760 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 * 30];
vector<int> rgp[maxn * 30];
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 174 ms 375252 KB Output is correct
2 Correct 170 ms 375084 KB Output is correct
3 Correct 168 ms 375100 KB Output is correct
4 Correct 194 ms 375076 KB Output is correct
5 Correct 175 ms 375124 KB Output is correct
6 Correct 178 ms 375048 KB Output is correct
7 Correct 188 ms 375100 KB Output is correct
8 Correct 189 ms 375168 KB Output is correct
9 Correct 180 ms 375072 KB Output is correct
10 Correct 169 ms 375088 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 375252 KB Output is correct
2 Correct 170 ms 375084 KB Output is correct
3 Correct 168 ms 375100 KB Output is correct
4 Correct 194 ms 375076 KB Output is correct
5 Correct 175 ms 375124 KB Output is correct
6 Correct 178 ms 375048 KB Output is correct
7 Correct 188 ms 375100 KB Output is correct
8 Correct 189 ms 375168 KB Output is correct
9 Correct 180 ms 375072 KB Output is correct
10 Correct 169 ms 375088 KB Output is correct
11 Correct 182 ms 379068 KB Output is correct
12 Correct 184 ms 379060 KB Output is correct
13 Correct 184 ms 379068 KB Output is correct
14 Correct 190 ms 378984 KB Output is correct
15 Correct 182 ms 379112 KB Output is correct
16 Correct 182 ms 379116 KB Output is correct
17 Correct 184 ms 379208 KB Output is correct
18 Correct 182 ms 379044 KB Output is correct
19 Correct 184 ms 379028 KB Output is correct
20 Correct 206 ms 379044 KB Output is correct
21 Correct 195 ms 379112 KB Output is correct
22 Correct 186 ms 379124 KB Output is correct
23 Correct 191 ms 379148 KB Output is correct
24 Correct 182 ms 379108 KB Output is correct
25 Correct 185 ms 379004 KB Output is correct
26 Correct 200 ms 379044 KB Output is correct
27 Correct 190 ms 379248 KB Output is correct
28 Correct 181 ms 379008 KB Output is correct
29 Correct 184 ms 379064 KB Output is correct
30 Correct 218 ms 379024 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 760 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 174 ms 375252 KB Output is correct
2 Correct 170 ms 375084 KB Output is correct
3 Correct 168 ms 375100 KB Output is correct
4 Correct 194 ms 375076 KB Output is correct
5 Correct 175 ms 375124 KB Output is correct
6 Correct 178 ms 375048 KB Output is correct
7 Correct 188 ms 375100 KB Output is correct
8 Correct 189 ms 375168 KB Output is correct
9 Correct 180 ms 375072 KB Output is correct
10 Correct 169 ms 375088 KB Output is correct
11 Correct 182 ms 379068 KB Output is correct
12 Correct 184 ms 379060 KB Output is correct
13 Correct 184 ms 379068 KB Output is correct
14 Correct 190 ms 378984 KB Output is correct
15 Correct 182 ms 379112 KB Output is correct
16 Correct 182 ms 379116 KB Output is correct
17 Correct 184 ms 379208 KB Output is correct
18 Correct 182 ms 379044 KB Output is correct
19 Correct 184 ms 379028 KB Output is correct
20 Correct 206 ms 379044 KB Output is correct
21 Correct 195 ms 379112 KB Output is correct
22 Correct 186 ms 379124 KB Output is correct
23 Correct 191 ms 379148 KB Output is correct
24 Correct 182 ms 379108 KB Output is correct
25 Correct 185 ms 379004 KB Output is correct
26 Correct 200 ms 379044 KB Output is correct
27 Correct 190 ms 379248 KB Output is correct
28 Correct 181 ms 379008 KB Output is correct
29 Correct 184 ms 379064 KB Output is correct
30 Correct 218 ms 379024 KB Output is correct
31 Runtime error 760 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -