Submission #1117756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117756		vjudge1	Paprike (COI18_paprike)	C++17	13 / 100	68 ms	8536 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int sz = 3e5 + 5;
vector<int> par(sz),comp(sz);

int FIND(int a){
    return (par[a] == a ? a : par[a] = FIND(par[a]));
}

void UNI(int a,int b){
    comp[b] += comp[a];
    par[a] = b;
}

signed main(){
    int n,k;
    cin >> n >> k;
    vector<int> sira(n+1);
    for(int i=1;i<=n;++i){
        cin >> sira[i];
        comp[i] = sira[i];
        par[i] = i;
    }
    int a,b;
    for(int i=1;i<n;++i){
        cin >> a >> b;
        a = FIND(a);
        b = FIND(b);
        if(a == b)continue;
        if(comp[a] + comp[b] > k)continue;
        UNI(a,b);
    }
    unordered_set<int> st;
    for(int i=1;i<=n;++i)st.insert(FIND(i));
    cout << st.size() - 1;

}

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