oj.uz

Submission #971417

# Submission time Handle Problem Language Result Execution time Memory
971417 2024-04-28T13:23:20 Z Nare_2007 Stranded Far From Home (BOI22_island) C++17
10 / 100
 215 ms 5980 KB 
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <string>
#define ll long long
using namespace std;
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define lli long long int 
vector<ll> g[2005];

void solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n + 1);
	for (ll i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (ll i = 0; i < m; ++i) {
		ll x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	string s = "";
	for (ll i = 1; i <= n; ++i) {
		priority_queue<pair<ll, ll>> q;
		vector<bool> vis(n + 1);
		ll cnt = 0;
		q.push({ -a[i], i });
		vis[i] = 1;
		bool b = 1;
		while (!q.empty()) {
			pair<ll, ll> p = q.top();
			q.pop();
			if(cnt && cnt < abs(p.first)) {
				s += '0';
				b = 0;
				break;
			}
			cnt += abs(p.first);
			for (auto x : g[p.second]) {
				if (!vis[x]) {
					q.push({ -a[x], x });
					vis[x] = 1;
				}
			}
		}
		if (b) {
			s += '1';
		}
	}
	cout << s << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 136 ms 616 KB Output is correct
5 Correct 130 ms 628 KB Output is correct
6 Correct 215 ms 848 KB Output is correct
7 Correct 133 ms 604 KB Output is correct
8 Correct 93 ms 604 KB Output is correct
9 Correct 211 ms 636 KB Output is correct
10 Correct 52 ms 604 KB Output is correct
11 Correct 46 ms 604 KB Output is correct
12 Correct 42 ms 604 KB Output is correct
13 Correct 84 ms 580 KB Output is correct
14 Correct 79 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Runtime error 18 ms 5972 KB Execution killed with signal 11
4 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 Runtime error 17 ms 5980 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 20 ms 5632 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 136 ms 616 KB Output is correct
5 Correct 130 ms 628 KB Output is correct
6 Correct 215 ms 848 KB Output is correct
7 Correct 133 ms 604 KB Output is correct
8 Correct 93 ms 604 KB Output is correct
9 Correct 211 ms 636 KB Output is correct
10 Correct 52 ms 604 KB Output is correct
11 Correct 46 ms 604 KB Output is correct
12 Correct 42 ms 604 KB Output is correct
13 Correct 84 ms 580 KB Output is correct
14 Correct 79 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 504 KB Output is correct
17 Runtime error 18 ms 5972 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -