Submission #603331

#	Time	Username	Problem	Language	Result	Execution time	Memory
603331		Zanite	Paprike (COI18_paprike)	C++17	0 / 100	1090 ms	6204 KiB

paprike

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

using pii	= pair<int, int>;
using ll	= long long;
using pll	= pair<ll, ll>;

#define fi	first
#define se	second

const int maxN	= 1e5 + 5;

int n;
ll k, h[maxN];
vector<pll> edges;

struct DSU {
	int n, cc;
	vector<int> par, sz;
	vector<ll> spice;

	DSU(int n) : n(n), cc(n) {
		par = sz = vector<int>(n+1, 1);
		spice.assign(n+1, 0);
		iota(par.begin(), par.end(), 0);
		for (int i = 1; i <= n; i++) {
			spice[i] = h[i];
		}
	}

	int rep(int x) {
		return ((x == par[x]) ? (x) : (par[x] = rep(par[x])));
	}

	bool check(int x, int y) {
		return (rep(x) == rep(y));
	}

	void join(int x, int y) {
		int a = rep(x), b = rep(y);
		if (a == b) return;
		if (sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
		spice[a] += spice[b];
		cc--;
	}

	ll checkSpice(int x, int y) {
		return spice[rep(x)] + spice[rep(y)];
	}
};

int main() {
	scanf("%d %lld", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &h[i]);
	}
	for (int u, v, i = 1; i < n; i++) {
		scanf("%d %d", &u, &v);
		edges.push_back({u, v});
	}

	DSU D = DSU(n);
	for (int i = 1; i < n; i++) {
		int mn = k+1, mu = -1, mv = -1;
		for (auto &[u, v] : edges) {
			if (D.check(u, v)) continue;
			ll S = D.checkSpice(u, v);
			if (S < mn) {
				mn = S;
				mu = u;
				mv = v;
			}
		}

		if (mu == -1) break;
		D.join(mu, mv);
	}
	
	printf("%d\n", D.cc - 1);
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d %lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
paprike.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
paprike.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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