Submission #1150373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150373		VMaksimoski008	Mergers (JOI19_mergers)	C++20	0 / 100	9 ms	15940 KiB

mergers

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 5e5 + 5;

struct union_find {
    int n;
    vector<int> par, size;
    union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return ;
        if(size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        par[b] = a;
    }
} dsu(maxn);

int n, k, in[maxn], out[maxn], mnT[maxn], mxT[maxn], mn[maxn], mx[maxn], t[maxn], timer = 0;
vector<int> G[maxn];

void dfs(int u, int p) {
    in[u] = timer++;
    mnT[t[u]] = min(mnT[t[u]], in[u]);
    mxT[t[u]] = max(mxT[t[u]], in[u]);

    for(int v : G[u])
        if(v != p) dfs(v, u);

    out[u] = timer - 1;
}

bool anc(int u, int x) {
    return in[u] <= x && x <= out[u];
}

void dfs2(int u, int p) {
    mn[u] = mnT[t[u]];
    mx[u] = mxT[t[u]];

    for(int v : G[u]) {
        if(v == p) continue;
        dfs2(v, u);
        mn[u] = min(mn[u], mn[v]);
        mx[u] = max(mx[u], mx[v]);
    }

    if(!anc(u, mn[u]) || !anc(u, mx[u]))
        dsu.uni(u, p);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> k;
    assert(n <= 100);
    vector<pii> E;
    for(int i=1; i<n; i++) {
        int a, b; cin >> a >> b;
        E.push_back({ a, b });
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i=1; i<=k; i++) mnT[i] = 1e9;
    for(int i=1; i<=n; i++) cin >> t[i];

    dfs(1, 1);
    dfs2(1, 1);

    int ans = 0;

    set<pii> st;
    for(auto [a, b] : E) {
        int x = min(dsu.find(a), dsu.find(b));
        int y = max(dsu.find(a), dsu.find(b));
        st.insert({ x, y });
    }

    vector<int> deg(n+1);
    for(auto [a, b] : st) {
        deg[a]++;
        deg[b]++;
    }

    for(int i=1; i<=n; i++)
        if(deg[i] == 1) ans++;
    cout << (ans + 1) / 2 << '\n';
}

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