oj.uz

Submission #993171

# Submission time Handle Problem Language Result Execution time Memory
993171 2024-06-05T12:03:36 Z prvocislo Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 506016 KB 
// meow cat, please meow back =^_^=

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int n, k;
const int logn = 18;
const int maxn = 200005 * (logn + 1);
int m;
vector<int> adj[maxn], adj_rev[maxn];
bool used[maxn], in[maxn];
int cnt[maxn];
vector<int> order, component;
void dfs1(int v) {
    used[v] = true;

    for (auto u : adj[v])
        if (!used[u])
            dfs1(u);

    order.push_back(v);
}

void dfs2(int v) {
    used[v] = true;
    component.push_back(v);

    for (auto u : adj_rev[v])
        if (!used[u])
            dfs2(u);
}
void add(int u, int v)
{
    adj[u].push_back(v);
    adj_rev[v].push_back(u);
}
int solve()
{
    fill(used, used + m, false);
    for (int i = 0; i < m; i++)
        if (!used[i])
            dfs1(i);
    fill(used, used + m, false);
    reverse(order.begin(), order.end());
    int ans = m;
    for (auto v : order)
        if (!used[v]) {
            dfs2(v);
            bool okay = true; int c = 0;
            for (int i : component) in[i] = true;
            for (int i : component)
            {
                if (cnt[i]) c++;
                for (int j : adj[i]) if (!in[j]) okay = false;
            }
            for (int i : component) in[i] = false;
            if (c && okay)
                ans = min(ans, c - 1);
            component.clear();
        }
    return ans;
}

vector<vector<int> > g, l, col;
vector<int> d, c;
void dfs(int u)
{
    for (int j = 1; j < logn; j++) l[j][u] = l[j - 1][l[j - 1][u]];
    for (int v : g[u]) if (v != l[0][u]) d[v] = d[u] + 1, l[0][v] = u, dfs(v);
}
int lca(int u, int v)
{
    if (d[u] < d[v]) swap(u, v);
    for (int i = logn - 1; i >= 0; i--) if (d[l[i][u]] >= d[v]) u = l[i][u];
    for (int i = logn - 1; i >= 0; i--) if (l[i][u] != l[i][v]) u = l[i][u], v = l[i][v];
    return u == v ? u : l[0][u];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    g.assign(n, {}), l.assign(logn, vector<int>(n, 0)), d.assign(n, 0), col.assign(k, {}), c.assign(n, -1);
    for (int i = 0, a, b; i < n - 1; i++) cin >> a >> b, g[--a].push_back(--b), g[b].push_back(a);
    for (int i = 0; i < n; i++)
    {
        cin >> c[i];
        col[--c[i]].push_back(i);
    }
    dfs(0);
    m = k + logn * n;
    for (int i = 0; i < n; i++)
    {
        add(k + i, c[i]);
        for (int b = 1; b < logn; b++) add(k + n * b + i, k + n * (b - 1) + i), add(k + n * b + i, k + n * (b - 1) + l[b - 1][i]);
    }
    for (int i = 0; i < k; i++)
    {
        cnt[i] = 1;
        int lc = col[i][0];
        for (int j : col[i]) lc = lca(lc, j);
        add(i, k + lc);
        for (int j : col[i])
        {
            for (int b = logn - 1; b >= 0; b--) if (d[l[b][j]] >= d[lc])
                add(i, k + b * n + j), j = l[b][j];
        }
    }
    cout << solve() << "\n";
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 178768 KB Output is correct
2 Correct 56 ms 178768 KB Output is correct
3 Correct 58 ms 178936 KB Output is correct
4 Correct 68 ms 178748 KB Output is correct
5 Correct 56 ms 178772 KB Output is correct
6 Correct 54 ms 178812 KB Output is correct
7 Correct 60 ms 178772 KB Output is correct
8 Correct 58 ms 178768 KB Output is correct
9 Correct 63 ms 178772 KB Output is correct
10 Correct 60 ms 178776 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 178768 KB Output is correct
2 Correct 56 ms 178768 KB Output is correct
3 Correct 58 ms 178936 KB Output is correct
4 Correct 68 ms 178748 KB Output is correct
5 Correct 56 ms 178772 KB Output is correct
6 Correct 54 ms 178812 KB Output is correct
7 Correct 60 ms 178772 KB Output is correct
8 Correct 58 ms 178768 KB Output is correct
9 Correct 63 ms 178772 KB Output is correct
10 Correct 60 ms 178776 KB Output is correct
11 Correct 71 ms 182736 KB Output is correct
12 Correct 74 ms 182740 KB Output is correct
13 Correct 71 ms 182748 KB Output is correct
14 Correct 70 ms 182564 KB Output is correct
15 Correct 75 ms 182088 KB Output is correct
16 Correct 88 ms 181980 KB Output is correct
17 Correct 73 ms 182364 KB Output is correct
18 Correct 71 ms 181996 KB Output is correct
19 Correct 70 ms 182416 KB Output is correct
20 Correct 69 ms 182096 KB Output is correct
21 Correct 71 ms 182096 KB Output is correct
22 Correct 69 ms 182096 KB Output is correct
23 Correct 75 ms 182812 KB Output is correct
24 Correct 72 ms 182040 KB Output is correct
25 Correct 72 ms 182096 KB Output is correct
26 Correct 75 ms 182096 KB Output is correct
27 Correct 74 ms 182100 KB Output is correct
28 Correct 73 ms 182096 KB Output is correct
29 Correct 87 ms 182160 KB Output is correct
30 Correct 72 ms 182104 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 506016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 178768 KB Output is correct
2 Correct 56 ms 178768 KB Output is correct
3 Correct 58 ms 178936 KB Output is correct
4 Correct 68 ms 178748 KB Output is correct
5 Correct 56 ms 178772 KB Output is correct
6 Correct 54 ms 178812 KB Output is correct
7 Correct 60 ms 178772 KB Output is correct
8 Correct 58 ms 178768 KB Output is correct
9 Correct 63 ms 178772 KB Output is correct
10 Correct 60 ms 178776 KB Output is correct
11 Correct 71 ms 182736 KB Output is correct
12 Correct 74 ms 182740 KB Output is correct
13 Correct 71 ms 182748 KB Output is correct
14 Correct 70 ms 182564 KB Output is correct
15 Correct 75 ms 182088 KB Output is correct
16 Correct 88 ms 181980 KB Output is correct
17 Correct 73 ms 182364 KB Output is correct
18 Correct 71 ms 181996 KB Output is correct
19 Correct 70 ms 182416 KB Output is correct
20 Correct 69 ms 182096 KB Output is correct
21 Correct 71 ms 182096 KB Output is correct
22 Correct 69 ms 182096 KB Output is correct
23 Correct 75 ms 182812 KB Output is correct
24 Correct 72 ms 182040 KB Output is correct
25 Correct 72 ms 182096 KB Output is correct
26 Correct 75 ms 182096 KB Output is correct
27 Correct 74 ms 182100 KB Output is correct
28 Correct 73 ms 182096 KB Output is correct
29 Correct 87 ms 182160 KB Output is correct
30 Correct 72 ms 182104 KB Output is correct
31 Execution timed out 3074 ms 506016 KB Time limit exceeded
32 Halted 0 ms 0 KB -