Submission #709559

#	Time	Username	Problem	Language	Result	Execution time	Memory
709559		aryan12	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1079 ms	18624 KiB

island

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
int n, m;
vector<int> g[N];
int a[N];

int greedy(int starting)
{
	int sum = a[starting], cnt = 1;
	vector<bool> vis(n + 1, false);
	vis[starting] = true;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	for(int to: g[starting])
	{
		pq.push({a[to], to});
	}
	while(!pq.empty())
	{
		auto [val, idx] = pq.top();
		pq.pop();
		if(vis[idx]) continue;
		if(sum < val)
		{
			break;
		}
		cnt++;
		sum += val;
		vis[idx] = true;
		for(int to: g[idx])
		{
			pq.push({a[to], to});
		}
	}
	return cnt;
}

void Solve() 
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
	{
		if(greedy(i) == n)
		{
			cout << '1';
		}
		else
		{
			cout << '0';
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35