oj.uz

Submission #709559

# Submission time Handle Problem Language Result Execution time Memory
709559 2023-03-13T23:05:55 Z aryan12 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 18624 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 315 ms 5076 KB Output is correct
5 Correct 258 ms 5076 KB Output is correct
6 Correct 499 ms 5160 KB Output is correct
7 Correct 341 ms 5156 KB Output is correct
8 Correct 261 ms 5128 KB Output is correct
9 Correct 441 ms 5160 KB Output is correct
10 Correct 151 ms 5076 KB Output is correct
11 Correct 141 ms 5076 KB Output is correct
12 Correct 131 ms 5076 KB Output is correct
13 Correct 362 ms 5264 KB Output is correct
14 Correct 161 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Execution timed out 1076 ms 18624 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1072 ms 13388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1079 ms 14636 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 315 ms 5076 KB Output is correct
5 Correct 258 ms 5076 KB Output is correct
6 Correct 499 ms 5160 KB Output is correct
7 Correct 341 ms 5156 KB Output is correct
8 Correct 261 ms 5128 KB Output is correct
9 Correct 441 ms 5160 KB Output is correct
10 Correct 151 ms 5076 KB Output is correct
11 Correct 141 ms 5076 KB Output is correct
12 Correct 131 ms 5076 KB Output is correct
13 Correct 362 ms 5264 KB Output is correct
14 Correct 161 ms 5076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 1076 ms 18624 KB Time limit exceeded
18 Halted 0 ms 0 KB -