oj.uz

답안 #706066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706066 2023-03-05T19:52:46 Z pakhomovee 수도 (JOI20_capital_city) C++17
11 / 100
 267 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 * 40];
vector<int> rgp[maxn * 40];
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 224 ms 498188 KB Output is correct
2 Correct 222 ms 498284 KB Output is correct
3 Correct 234 ms 498244 KB Output is correct
4 Correct 227 ms 498196 KB Output is correct
5 Correct 228 ms 498324 KB Output is correct
6 Correct 223 ms 498248 KB Output is correct
7 Correct 225 ms 498292 KB Output is correct
8 Correct 248 ms 498180 KB Output is correct
9 Correct 227 ms 498280 KB Output is correct
10 Correct 227 ms 498220 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 498188 KB Output is correct
2 Correct 222 ms 498284 KB Output is correct
3 Correct 234 ms 498244 KB Output is correct
4 Correct 227 ms 498196 KB Output is correct
5 Correct 228 ms 498324 KB Output is correct
6 Correct 223 ms 498248 KB Output is correct
7 Correct 225 ms 498292 KB Output is correct
8 Correct 248 ms 498180 KB Output is correct
9 Correct 227 ms 498280 KB Output is correct
10 Correct 227 ms 498220 KB Output is correct
11 Correct 234 ms 502140 KB Output is correct
12 Correct 240 ms 502164 KB Output is correct
13 Correct 236 ms 502096 KB Output is correct
14 Correct 241 ms 502208 KB Output is correct
15 Correct 267 ms 502204 KB Output is correct
16 Correct 234 ms 502276 KB Output is correct
17 Correct 245 ms 502208 KB Output is correct
18 Correct 235 ms 502200 KB Output is correct
19 Correct 236 ms 502228 KB Output is correct
20 Correct 239 ms 502184 KB Output is correct
21 Correct 244 ms 502208 KB Output is correct
22 Correct 235 ms 502268 KB Output is correct
23 Correct 238 ms 502184 KB Output is correct
24 Correct 244 ms 502216 KB Output is correct
25 Correct 239 ms 502248 KB Output is correct
26 Correct 245 ms 502200 KB Output is correct
27 Correct 233 ms 502172 KB Output is correct
28 Correct 233 ms 502116 KB Output is correct
29 Correct 238 ms 502328 KB Output is correct
30 Correct 237 ms 502136 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 498188 KB Output is correct
2 Correct 222 ms 498284 KB Output is correct
3 Correct 234 ms 498244 KB Output is correct
4 Correct 227 ms 498196 KB Output is correct
5 Correct 228 ms 498324 KB Output is correct
6 Correct 223 ms 498248 KB Output is correct
7 Correct 225 ms 498292 KB Output is correct
8 Correct 248 ms 498180 KB Output is correct
9 Correct 227 ms 498280 KB Output is correct
10 Correct 227 ms 498220 KB Output is correct
11 Correct 234 ms 502140 KB Output is correct
12 Correct 240 ms 502164 KB Output is correct
13 Correct 236 ms 502096 KB Output is correct
14 Correct 241 ms 502208 KB Output is correct
15 Correct 267 ms 502204 KB Output is correct
16 Correct 234 ms 502276 KB Output is correct
17 Correct 245 ms 502208 KB Output is correct
18 Correct 235 ms 502200 KB Output is correct
19 Correct 236 ms 502228 KB Output is correct
20 Correct 239 ms 502184 KB Output is correct
21 Correct 244 ms 502208 KB Output is correct
22 Correct 235 ms 502268 KB Output is correct
23 Correct 238 ms 502184 KB Output is correct
24 Correct 244 ms 502216 KB Output is correct
25 Correct 239 ms 502248 KB Output is correct
26 Correct 245 ms 502200 KB Output is correct
27 Correct 233 ms 502172 KB Output is correct
28 Correct 233 ms 502116 KB Output is correct
29 Correct 238 ms 502328 KB Output is correct
30 Correct 237 ms 502136 KB Output is correct
31 Runtime error 257 ms 524288 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -