Submission #43918

#	Time	Username	Problem	Language	Result	Execution time	Memory
43918		Waschbar	Paprike (COI18_paprike)	C++17	100 / 100	207 ms	17712 KiB

paprike

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
 
const int MAXN = 1e5;
 
int n, k, ans;
int sp[MAXN+1];
vector < vector < int > > g(MAXN+1);
 
long long DFS(int f, int p) {
        long long cnt = 0;
        vector < long long > v;
        cnt = sp[f];
 
        for(int i = 0; i < g[f].size(); i++) {
            int to = g[f][i];
            if(to == p) continue;
            long long x = DFS(to,f);
            cnt += x;
            v.push_back(x);
        }
 
        if(cnt <= k) return cnt;
 
        cnt = sp[f];
        sort(v.begin(),v.end());
        ans += v.size();
        for(int i = 0; i < v.size(); i++) {
            if(cnt+v[i] <= k) {cnt += v[i]; ans--;}
            else break;
        }
 
        return cnt;
}
 
int main() {
 
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
 
    cin >> n >> k;
 
    for(int i = 1; i <= n; i++)
        cin >> sp[i];
 
    for(int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
 
    DFS(1,0);
 
    cout << ans << endl;
 
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'long long int DFS(int, int)':
paprike.cpp:17:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < g[f].size(); i++) {
                        ~~^~~~~~~~~~~~~
paprike.cpp:30:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v.size(); i++) {
                        ~~^~~~~~~~~~

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