oj.uz

Submission #578127

# Submission time Handle Problem Language Result Execution time Memory
578127 2022-06-16T05:23:52 Z 8e7 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 13624 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...); }
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxc 31
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
vector<int> adj[maxn];
ll w[maxn];
int lev[maxn];

bool vis[maxn];

int main() {
	io
	int n, m;
	cin >> n >> m;
	ll tot = 0;
	for (int i = 1;i <= n;i++) cin >> w[i], tot += w[i];
	for (int i = 0;i < m;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string ans;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) vis[j] = 0;
		priority_queue<pii, vector<pii>, greater<pii> > pq;	
		pq.push({w[i], i});
		ll sum = 0;
		bool poss = 1;
		while (pq.size()) {
			auto [val, cur] = pq.top();pq.pop();
			if (sum != 0 && sum < val) {
				poss = 0;
				break;
			}
			sum += val;
			vis[cur] = 1;
			for (int v:adj[cur]) {
				if (!vis[v]) {
					vis[v] = 1;
					pq.push({w[v], v});
				}
			}
		}
		if (poss) ans += '1';
		else ans += '0';
	}
	cout << ans << "\n";
}
/*

6 7 
8 5 4 4 6 20
1 2
1 3
1 4
2 3
2 4
1 5
5 6
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 166 ms 5092 KB Output is correct
5 Correct 146 ms 5088 KB Output is correct
6 Correct 197 ms 5084 KB Output is correct
7 Correct 163 ms 5076 KB Output is correct
8 Correct 107 ms 5080 KB Output is correct
9 Correct 207 ms 5076 KB Output is correct
10 Correct 69 ms 5076 KB Output is correct
11 Correct 68 ms 5060 KB Output is correct
12 Correct 63 ms 5096 KB Output is correct
13 Correct 114 ms 5076 KB Output is correct
14 Correct 98 ms 5112 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 1077 ms 13624 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 1087 ms 12964 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 13080 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 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 166 ms 5092 KB Output is correct
5 Correct 146 ms 5088 KB Output is correct
6 Correct 197 ms 5084 KB Output is correct
7 Correct 163 ms 5076 KB Output is correct
8 Correct 107 ms 5080 KB Output is correct
9 Correct 207 ms 5076 KB Output is correct
10 Correct 69 ms 5076 KB Output is correct
11 Correct 68 ms 5060 KB Output is correct
12 Correct 63 ms 5096 KB Output is correct
13 Correct 114 ms 5076 KB Output is correct
14 Correct 98 ms 5112 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 1077 ms 13624 KB Time limit exceeded
18 Halted 0 ms 0 KB -