Submission #1117883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117883		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	50 ms	19916 KiB

paprike

//Author RufatM
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1e9+7
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int, int>
#define pb push_back
#define pii pair<ll, int>
#define all(a) a.begin(), a.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
vi adj[100001];
ll dp[100001], value[100001];
ll limit;
int res;
void dfs(int node, int parent) {
    dp[node] = value[node];
    vi subTree;
    for (int child : adj[node]) {
        if (child != parent) {
            dfs(child, node);
            dp[node] += dp[child];
            subTree.pb(dp[child]);
        }
    }
    sort(all(subTree), greater<int>());
    int idx = 0;

    while (dp[node] > limit) {
        res++;
        dp[node] -= subTree[idx++];
    }
}
signed main() {
    int t=1;
    //cin >> t;
    while(t--){
    fastio;
    int n;
    cin >> n >> limit;
    for (int i = 1; i <= n; ++i) cin >> value[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1, 0);
    cout << res << '\n';
    }
}

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