Submission #123184

#	Time	Username	Problem	Language	Result	Execution time	Memory
123184		tmwilliamlin168	Paprike (COI18_paprike)	C++14	100 / 100	66 ms	16504 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, k, ans;
long long h[mxN];
vector<int> adj[mxN];

void dfs(int u=0, int p=-1) {
	if(~p)
		adj[u].erase(find(adj[u].begin(), adj[u].end(), p));
	for(int v : adj[u]) {
		dfs(v, u);
		h[u]+=h[v];
	}
	sort(adj[u].begin(), adj[u].end(), [](const int &i, const int &j) {
		return h[i]>h[j];
	});
	for(int i=0; i<adj[u].size()&&h[u]>k; ++i, ++ans)
		h[u]-=h[adj[u][i]];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for(int i=0; i<n; ++i)
		cin >> h[i];
	for(int i=1, u, v; i<n; ++i) {
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs();
	cout << ans;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int, int)':
paprike.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[u].size()&&h[u]>k; ++i, ++ans)
               ~^~~~~~~~~~~~~~

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