oj.uz

Submission #603331

# Submission time Handle Problem Language Result Execution time Memory
603331 2022-07-24T03:26:13 Z Zanite Paprike (COI18_paprike) C++17
0 / 100
 1000 ms 6204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 6204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -