Submission #1117669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117669		vjudge1	Paprike (COI18_paprike)	C++17	0 / 100	1154 ms	1048576 KiB

paprike

// author - alimammadzade

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;
int p[N];
int _find(int u) { return (p[u] < 0 ? u : p[u] = _find(p[u])); }
void _union(int u, int v) { if (p[v] < p[u]) swap(u, v); p[u] += p[v], p[v] = u; }

signed main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    // system("cls"), freopen("in.txt", "r", stdin);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) { cin >> p[i]; p[i] = -p[i]; }
    int res = n - 1;
    vector<array<int, 2>> e(n - 1);
    for (auto& [u, v] : e) cin >> u >> v;
    for (auto [u, v] : e) {
        u = _find(u), v = _find(v);
        if (u != v and -p[u] - p[v] <= k) { res--; _union(u, v); }
    }
    cout << res;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49