Submission #240748

#	Time	Username	Problem	Language	Result	Execution time	Memory
240748		NONAME	Paprike (COI18_paprike)	C++14	13 / 100	72 ms	16888 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 500;

int n, limit, a[N], total[N], pr[N];
vector <int> g[N];

int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }

void unite(int x, int y) { pr[f(y)] = f(x); }

void dfs(int v, int pred = -1) {
    for (int to : g[v]) {
        if (to == pred)
            continue;
            
        int x = f(v), y = f(to);
        
        if (total[x] + total[y] <= limit)
            total[x] += total[y], unite(x, y);
            
        dfs(to, v);
    }
}

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

    cin >> n >> limit;
    for (int i = 0; i < n; ++i)
        cin >> a[i], pr[i] = i, total[i] = a[i];
        
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    dfs(0);
    
    set <int> s;
    s.clear();
    
    for (int i = 0; i < n; ++i)
        s.insert(f(i));
        
    cout << int(s.size()) - 1 << "\n";
}

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