Submission #111098

#	Time	Username	Problem	Language	Result	Execution time	Memory
111098		rzbt	Paprike (COI18_paprike)	C++14	0 / 100	84 ms	16844 KiB

paprike

#include <bits/stdc++.h>
#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;
vector<int> niz[MAXN];
int spice[MAXN],otac[MAXN],stepen[MAXN];
int uk,res;

set<pair<int,int> > listovi;
void dfs(int t,int o){
    int broj=0;
    otac[t]=o;
    for(auto x:niz[t]){
        if(x==o)continue;
        broj++;
        dfs(x,t);
    }
    if(!broj)listovi.insert(make_pair(spice[t],t));
    else stepen[t]=broj;
}

int main()
{
    scanf("%d %d", &n, &k);
    for(int i=1;i<=n;i++){
        scanf("%d", spice+i);
        uk+=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);
    while(!listovi.empty()){

        if(uk<=k){
            res++;
        }
        int t=listovi.begin()->second;
        //printf(" %d %d %d\n",t,otac[t],spice[t]);
        if(t==1){

            break;
        }
        listovi.erase(listovi.begin());
        if(spice[otac[t]]+spice[t]>k){
            res++;
        }else{
            spice[otac[t]]+=spice[t];
        }
        stepen[otac[t]]--;
        if(!stepen[otac[t]])listovi.insert(mp(spice[otac[t]],otac[t]));

    }
    printf("%d",res);

    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:33: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:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", spice+i);
         ~~~~~^~~~~~~~~~~~~~~
paprike.cpp:40: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: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49