(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #256646

#TimeUsernameProblemLanguageResultExecution timeMemory
256646uacoder123Paprike (COI18_paprike)C++14
100 / 100
100 ms44664 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; vi al[100001]; lli val[100001],ans=0; vi v[1000001]; int n,k; void dfs(int node,int par) { for(int i=0;i<al[node].size();++i) { if(al[node][i]!=par) { dfs(al[node][i],node); val[node]+=val[al[node][i]]; v[node].pb(val[al[node][i]]); } } sort(all(v[node])); while(val[node]>k) { val[node]-=v[node].back(); v[node].pop_back(); ans++; } v[node].clear(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>k; for(int i=1;i<=n;++i) cin>>val[i]; for(int i=0;i<n-1;++i) { int f,s; cin>>f>>s; al[f].pb(s); al[s].pb(f); } dfs(1,1); cout<<ans<<endl; return(0); }

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int, int)':
paprike.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...