oj.uz

Submission #670788

# Submission time Handle Problem Language Result Execution time Memory
670788 2022-12-10T13:55:28 Z Kahou Capital City (JOI20_capital_city) C++14
11 / 100
 3000 ms 514492 KB 
/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50, LG = 18, M = 4e6 + 50;
int n, k, c[N], h[N], m, id[LG][N], par[LG][N];
bool mark[M];
bool vis[M];
int scc[M], cnt[M];
vector<int> topol;
vector<int> adj[N], adj2[2][M];
vector<int> vc[N];
int t;

void dfs(int u, int p) {
        h[u] = h[p]+1;
        par[0][u] = p;
        adj2[0][id[0][u]].push_back(c[u]);
        adj2[1][c[u]].push_back(id[0][u]);
        for (int v:adj[u]) {
                if (v == p) continue;
                dfs(v, u);
        }
}
int LCA(int u, int v) {
        if (h[u] > h[v]) swap(u, v);
        for (int x = LG-1; x >= 0; x--) {
                if ((h[v]-h[u])>>x&1) v = par[x][v];
        }
        for (int x = LG-1; x >= 0; x--) {
                if (par[x][u] != par[x][v]) u = par[x][u], v= par[x][v];
        }
        if (u == v) return u;
        return par[0][u];
}
void add_edge(int u, int v) {
        int x = c[u];
        for (int t = LG-1; t >= 0; t--) {
                if ((h[u]-h[v]+1)>>t&1) {
                        adj2[0][x].push_back(id[t][u]);
                        adj2[1][id[t][u]].push_back(x);
                        u = par[t][u];
                }
        }
}
void dfs2(int u) {
        vis[u] = 1;
        for (int v:adj2[1][u]){
                if (vis[v]) continue;
                dfs2(v);
        }
        topol.push_back(u);
}
void sfd(int u) {
        scc[u] = t;
        for (int v:adj2[0][u]) {
                if (scc[v]) {
                        mark[t] = mark[t] || (scc[v] != t);
                        continue;
                }
                sfd(v);
        }
}

void solve() {
        cin >> n >> k;
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v), adj[v].push_back(u);
        }
        for (int u = 1; u <= n; u++) {
                cin >> c[u];
                vc[c[u]].push_back(u);
        }
        m = k;
        for (int x = 0; x < LG; x++) {
                for (int u = 1; u <= n; u++) {
                        id[x][u] = ++m;
                }
        }
        dfs(1, 0);
        for (int x = 1; x < LG; x++) {
                for (int u = 1; u <= n; u++) {
                        par[x][u] = par[x-1][par[x-1][u]];
                        adj2[0][id[x][u]].push_back(id[x-1][u]);
                        adj2[0][id[x][u]].push_back(id[x-1][par[x-1][u]]);
                        adj2[1][id[x-1][u]].push_back(id[x][u]);
                        adj2[1][id[x-1][par[x-1][u]]].push_back(id[x][u]);
                }
        }
        for (int x = 1; x <= k; x++) {
                int r = vc[x][0];
                for (int u : vc[x]) {
                        r = LCA(r, u);
                }
                for (int u : vc[x]) {
                        add_edge(u, r);
                }
        }

        for (int u = 1; u <= m; u++) {
                if (!vis[u]) dfs2(u);
        }
        reverse(topol.begin(), topol.end());
        for (int u:topol) {
                if (!scc[u]) {
                        t++;
                        sfd(u);
                }
        }
        for (int x = 1; x <= k; x++) {
                cnt[scc[x]]++;
        }

        int ans = N;
        for (int x = 1; x <= t; x++) {
                if (mark[x]) continue;
                ans = min(ans, cnt[x]);
        }
        cout << ans-1 << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 197836 KB Output is correct
2 Correct 88 ms 197768 KB Output is correct
3 Correct 88 ms 197792 KB Output is correct
4 Correct 87 ms 197748 KB Output is correct
5 Correct 90 ms 197804 KB Output is correct
6 Correct 88 ms 197844 KB Output is correct
7 Correct 88 ms 197748 KB Output is correct
8 Correct 92 ms 197840 KB Output is correct
9 Correct 88 ms 197768 KB Output is correct
10 Correct 88 ms 197796 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 197836 KB Output is correct
2 Correct 88 ms 197768 KB Output is correct
3 Correct 88 ms 197792 KB Output is correct
4 Correct 87 ms 197748 KB Output is correct
5 Correct 90 ms 197804 KB Output is correct
6 Correct 88 ms 197844 KB Output is correct
7 Correct 88 ms 197748 KB Output is correct
8 Correct 92 ms 197840 KB Output is correct
9 Correct 88 ms 197768 KB Output is correct
10 Correct 88 ms 197796 KB Output is correct
11 Correct 97 ms 201080 KB Output is correct
12 Correct 112 ms 201072 KB Output is correct
13 Correct 99 ms 201032 KB Output is correct
14 Correct 98 ms 201024 KB Output is correct
15 Correct 106 ms 201200 KB Output is correct
16 Correct 99 ms 201168 KB Output is correct
17 Correct 99 ms 201092 KB Output is correct
18 Correct 102 ms 201100 KB Output is correct
19 Correct 99 ms 201192 KB Output is correct
20 Correct 107 ms 201176 KB Output is correct
21 Correct 108 ms 201236 KB Output is correct
22 Correct 99 ms 201120 KB Output is correct
23 Correct 101 ms 201188 KB Output is correct
24 Correct 96 ms 201024 KB Output is correct
25 Correct 101 ms 201036 KB Output is correct
26 Correct 100 ms 201068 KB Output is correct
27 Correct 99 ms 201100 KB Output is correct
28 Correct 101 ms 201068 KB Output is correct
29 Correct 98 ms 201092 KB Output is correct
30 Correct 98 ms 201072 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 197836 KB Output is correct
2 Correct 88 ms 197768 KB Output is correct
3 Correct 88 ms 197792 KB Output is correct
4 Correct 87 ms 197748 KB Output is correct
5 Correct 90 ms 197804 KB Output is correct
6 Correct 88 ms 197844 KB Output is correct
7 Correct 88 ms 197748 KB Output is correct
8 Correct 92 ms 197840 KB Output is correct
9 Correct 88 ms 197768 KB Output is correct
10 Correct 88 ms 197796 KB Output is correct
11 Correct 97 ms 201080 KB Output is correct
12 Correct 112 ms 201072 KB Output is correct
13 Correct 99 ms 201032 KB Output is correct
14 Correct 98 ms 201024 KB Output is correct
15 Correct 106 ms 201200 KB Output is correct
16 Correct 99 ms 201168 KB Output is correct
17 Correct 99 ms 201092 KB Output is correct
18 Correct 102 ms 201100 KB Output is correct
19 Correct 99 ms 201192 KB Output is correct
20 Correct 107 ms 201176 KB Output is correct
21 Correct 108 ms 201236 KB Output is correct
22 Correct 99 ms 201120 KB Output is correct
23 Correct 101 ms 201188 KB Output is correct
24 Correct 96 ms 201024 KB Output is correct
25 Correct 101 ms 201036 KB Output is correct
26 Correct 100 ms 201068 KB Output is correct
27 Correct 99 ms 201100 KB Output is correct
28 Correct 101 ms 201068 KB Output is correct
29 Correct 98 ms 201092 KB Output is correct
30 Correct 98 ms 201072 KB Output is correct
31 Execution timed out 3139 ms 514492 KB Time limit exceeded
32 Halted 0 ms 0 KB -