Submission #43878

#	Time	Username	Problem	Language	Result	Execution time	Memory
43878		ngkan146	Paprike (COI18_paprike)	C++11	100 / 100	94 ms	44348 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
int n,cnt,val,w[100005];
vector <int> G[100005];
int dfs(int u,int p){
    int res = w[u];
    vector <int> child;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if (v == p) continue;
        child.push_back(dfs(v,u));
    }
    sort(child.begin(),child.end());
    int last = 0;
    for(last = 0;last < child.size();last ++)
        if (res + child[last] > val) break;
        else res += child[last];
    cnt += child.size() - last;
    return res;
}
int solve(){
    cnt = 0;
    dfs(1,1);
    return cnt;
}
int main(){
    scanf("%d %d",&n,&val);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    printf("%d",solve());
}

Compilation message (stderr)

paprike.cpp: In function 'int dfs(int, int)':
paprike.cpp:8:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[u].size();i++){
                 ~^~~~~~~~~~~~
paprike.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(last = 0;last < child.size();last ++)
                  ~~~~~^~~~~~~~~~~~~~
paprike.cpp: In function 'int main()':
paprike.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&val);
     ~~~~~^~~~~~~~~~~~~~~~~
paprike.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&w[i]);
         ~~~~~^~~~~~~~~~~~
paprike.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

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