Submission #682031

#	Time	Username	Problem	Language	Result	Execution time	Memory
682031		ParsaS	Mergers (JOI19_mergers)	C++17	100 / 100	1141 ms	102928 KiB

mergers

// In the name of God
//-MILY-
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 5e5 + 5;
int n, k;
vector<int> adj[N], vec[N];
int mn[N], tin[N], tout[N], T;
int ans, h[N], cnt, c[N];
bool vis[N], mark[N];

void dfs(int v, int p) {
    tin[v] = ++T;
    for (auto u : adj[v]) {
        if (u == p)
            continue;
        dfs(u, v);
    }
    tout[v] = ++T;
}
void dfs2(int v, int p) {
    vis[v] = true;
    mn[v] = h[v];
    bool tmp = false;
    for (auto u : adj[v]) {
        if (!vis[u]) {
            h[u] = h[v] + 1;
            dfs2(u, v);
            if (mn[u] > h[v]) {
                mark[u] = true;
                cnt++;
            }
            mn[v] = min(mn[v], mn[u]);
        }
        else if (u != p || tmp) {
            mn[v] = min(mn[v], h[u]);
        }
        if (u == p)
            tmp = true;
    }
}
void dfs3(int v) {
    vis[v] = true;
    for (auto u : adj[v]) {
        if (!vis[u]) {
            dfs3(u);
            c[v] += c[u];
            if (mark[u])
                c[v]++;
        }
    }
    ans += mark[v] && (c[v] == 0 || c[v] == cnt - 1);
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int v, u; cin >> v >> u;
        adj[v].pb(u), adj[u].pb(v);
    }
    for (int i = 1; i <= n; i++) {
        int s; cin >> s;
        vec[s].pb(i);
    }
    dfs(1, 0);
    for (int i = 1; i <= k; i++) {
        vector<pair<int, int> > V;
        for (auto v : vec[i]) {
            V.pb(mp(tin[v], v));
        }
        sort(V.begin(), V.end());
        for (int i = 0; i < (int)V.size(); i++) {
            int j = (i + 1) % (int)V.size();
            adj[V[i].se].pb(V[j].se);
            adj[V[j].se].pb(V[i].se);
        }
    }
    dfs2(1, 0);
    memset(vis, 0, sizeof vis);
    dfs3(1);
    cout << (ans + 1) / 2 << '\n';
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30