Submission #169466

#	Time	Username	Problem	Language	Result	Execution time	Memory
169466		rzbt	Paprike (COI18_paprike)	C++14	100 / 100	121 ms	23056 KiB

paprike

#include <cstdio>
#include <algorithm>
#include <vector>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

int n,k,spice[MAXN];
int res=0;
vector<int> deca[MAXN],niz[MAXN];


int dfs(int t,int o){
    for(auto x:niz[t]){
        if(x==o)continue;
        deca[t].pb(dfs(x,t));
    }
    sort(all(deca[t]));
    int tz=spice[t];
    for(auto x:deca[t]){
        if(tz+x<=k)tz+=x;
        else res++;
    }
    return tz;
}

int main()
{
    scanf("%d %d", &n, &k);
    for(int i=1;i<=n;i++)
        scanf("%d",spice+i);
    for(int i=1;i<n;i++){
        int t1,t2;
        scanf("%d %d", &t1, &t2);
        niz[t1].pb(t2);
        niz[t2].pb(t1);
    }
    dfs(1,0);
    printf("%d",res);

    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
paprike.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",spice+i);
         ~~~~~^~~~~~~~~~~~~~
paprike.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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