Submission #1117742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117742		vjudge1	Paprike (COI18_paprike)	C++17	0 / 100	1002 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) { 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 = 0;
    vector<array<int, 2>> e(n - 1);
    for (auto& [u, v] : e) {
        cin >> u >> v;
        int pu = _find(u), pv = _find(v);
        if (pu != pv and -p[pu] - p[pv] <= k) _union(pu, pv);
    }
    for (auto& [u, v] : e) res += (_find(u) != _find(v));
    cout << res;
}

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