Submission #44614

#	Time	Username	Problem	Language	Result	Execution time	Memory
44614		ulna	Paprike (COI18_paprike)	C++11	100 / 100	93 ms	28488 KiB

paprike

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

// why am I so weak

int n;
long long  k;
int a[100055];
int cut[100055];
long long dp[100055];

int pt[100055];
vector<int> g[100055];

typedef pair<long long, int> P;

#define ft first
#define sd second

bool cutted[100055];

void dfs(int v, int par = -1) {
	dp[v] = a[v];

	for (auto u : g[v]) if (u != par) {
		dfs(u, v);
		dp[v] += dp[u];
		cut[v] += cut[u];
	}

	sort(g[v].begin(), g[v].end(), [&] (int u, int v) {
		return dp[u] > dp[v];
	});

	pt[v] = 0;

	for (int i = 0; i < (int)g[v].size(); i++) {
		int u = g[v][i];

		if (u == par) continue;

		if (dp[v] <= k) {
			pt[v] = i;
			break;
		}

		cut[v]++;
		cutted[u] = true;
		dp[v] -= dp[u];
	}
}

int res = INT_MAX;

void rdfs(int v, int par = -1, P ac = P(0, 0)) {
	dp[v] += ac.ft;

	int sub = 0;
	bool cut_p = false;

	if (dp[v] > k) {
		sub = ac.sd + cut[v] + 1;

		long long high = 0;
		int id = -1;

		for (auto u : g[v]) if (u != par && !cutted[u]) {
			if (dp[u] > high) high = dp[u], id = u;
		}

		high = max(high, ac.ft);

		dp[v] -= high;

		if (high > ac.ft) cutted[id] = true;
		else cut_p = true;
	} else {
		sub = ac.sd + cut[v];
	}

	res = min(res, sub);

	long long low = LLONG_MAX;

	for (auto u : g[v]) if (u != par) {
		if (cutted[u]) {
			low = min(low, dp[u]);
			rdfs(u, v, P(dp[v], sub - cut[u] - 1));
		} else {
			int spe = 0;
			long long sl = LLONG_MAX;

			if (low != LLONG_MAX) sl = min(sl, low);
			if (cut_p) sl = min(sl, ac.ft);

			long long cur = dp[v] - dp[u];

			if (sl != LLONG_MAX && cur + sl <= k) {
				cur += sl;
				spe = 1;
			}

			rdfs(u, v, P(cur, sub - cut[u] - spe));
		}
	}
}
int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) scanf("%d", &a[i]);

	for (int i = 0; i + 1 < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--, y--;

		g[x].push_back(y);
		g[y].push_back(x);
	}

	dfs(0);
	rdfs(0);
	
	printf("%d\n", res);

	return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:110:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
                              ~~~~~^~~~~~~~~~~~~
paprike.cpp:114:8: 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