Submission #240751

#	Time	Username	Problem	Language	Result	Execution time	Memory
240751		NONAME	Paprike (COI18_paprike)	C++14	100 / 100	93 ms	19192 KiB

paprike

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

const int N = 1e5 + 500;

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

int dfs(int v, int pred = -1) {
    vector <ll> vec;
    vec.clear();
    
    int res = 0;
    
    for (int to : g[v]) {
        if (to == pred)
            continue;
            
        res += dfs(to, v);
        
        total[v] += total[to];
        vec.push_back(total[to]);
    }
    
    sort(vec.rbegin(), vec.rend());

    for (int i : vec) {
        if (total[v] <= limit)
            break;
            
        total[v] -= i;
        ++res;
    }
    
    return res;
}

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 >> total[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);
    }
    
    cout << dfs(0) << "\n";
}

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