Submission #46197

#	Time	Username	Problem	Language	Result	Execution time	Memory
46197		Bruteforceman	Paprike (COI18_paprike)	C++11	0 / 100	1079 ms	4996 KiB

paprike

#include "bits/stdc++.h"
using namespace std;
int l[100010], r[100010];
int h[100010];
int par[100010];
long long cost[100010];
bool use[100010];
const long long inf = 1e15;

int root(int x) {
	if(par[x] == x) return x;
	return par[x] = root(par[x]);
}
void join(int x, int y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		par[x] = y;
		cost[y] += cost[x];
	}
}
 
int main(int argc, char const *argv[])
{
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> h[i];
	for(int i = 1; i < n; i++) {
		cin >> l[i] >> r[i];
	}
	for(int i = 1; i <= n; i++) {
		cost[i] = h[i];
		par[i] = i;
	}
	int ans = n-1;
	for(int x = 1; x < n; x++) {
		int opt = -1;
		long long least = inf;
		for(int i = 1; i < n; i++) {
			if(use[i] == false) {
				long long c = cost[root(l[i])] + cost[root(r[i])];
				if(opt == -1 || least > c) {
					least = c;
					opt = i;
				}
			}	
	 	}
	 	if(least <= k) {
	 		join(l[opt], r[opt]);
	 		use[opt] = true;
	 		--ans;
	 	} else {
	 		break;
	 	}
	}
	printf("%d\n", ans);
	return 0;
}

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