oj.uz

Submission #1098971

# Submission time Handle Problem Language Result Execution time Memory
1098971 2024-10-10T11:44:59 Z ohad Stranded Far From Home (BOI22_island) C++14
0 / 100
 194 ms 27032 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
void init(ll n, vll& par) {
	for (ll i = 0; i < n; i++)
	{
		par[i] = i;
	}
}
ll find(ll a, vll& par) {
	if (par[a] == a)
		return a;
	return par[a] = find(par[a], par);
}

int main() {
	ll n, m;
	cin >> n >> m;
	vll num(n);
	for (auto& i : num)
	{
		cin >> i;
	}
	vector<vll> nei(n);
	for (int i = 0; i < m; i++)
	{
		ll a, b;
		cin >> a >> b;
		nei[a - 1].push_back(b - 1);
		nei[b - 1].push_back(a - 1);
	}
	vll par(n);
	vll overtake(n);
	init(n, par);
	init(n, overtake);
	vector<pair<ll, ll>> pairs;
	vll visited(n, 0);

	for (int i = 0; i < n; i++)
	{
		pairs.push_back({ num[i],i });
	}
	sort(pairs.begin(), pairs.end());

	for (int i = 0; i < n; i++)
	{
		ll v = pairs[i].second;
		ll cost = pairs[i].first;
		visited[v] = 1;
		for (int u : nei[v])
		{
			if (!visited[u])
				continue;
			u = find(u, par);
			if (u == v)
				continue;
			num[v] += num[u];
			par[u] = v;
			if (num[u] >= cost)
				overtake[u] = v;
		}
	}
	ll v = pairs[n - 1].second;
	for (int i = 0; i < n; i++)
	{
		if (find(i, overtake) == v)
			cout << 1 << " ";
		else
			cout << 0 << " ";
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 179 ms 26032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 194 ms 27032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -