oj.uz

Submission #744918

# Submission time Handle Problem Language Result Execution time Memory
744918 2023-05-19T08:11:11 Z josanneo22 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 19644 KB 
#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
#define int long long
const int maxn = 2e5 + 50;
vector<vector<int>> adj(maxn);
vector<int>vis(maxn), s(maxn);
int tot;
void run(int u) {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(mp(0LL, u));
	while (pq.size()) {
		pii uu = pq.top(); pq.pop();
		if (vis[uu.se] || uu.fi > tot) continue; 
		vis[uu.se] = 1; tot += uu.fi;
		for (auto& v : adj[uu.se]) {
			pq.push(mp(s[v], v));
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> s[i];
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) vis[j] = 0;
		tot = s[i]; run(i);
		int ok = 1; for (int j = 0; j < n; j++) ok &= vis[j];
		cout << ok;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 314 ms 8148 KB Output is correct
5 Correct 264 ms 8276 KB Output is correct
6 Correct 456 ms 8160 KB Output is correct
7 Correct 342 ms 8412 KB Output is correct
8 Correct 252 ms 8264 KB Output is correct
9 Correct 449 ms 8420 KB Output is correct
10 Correct 161 ms 8208 KB Output is correct
11 Correct 149 ms 8248 KB Output is correct
12 Correct 134 ms 8276 KB Output is correct
13 Correct 362 ms 8268 KB Output is correct
14 Correct 166 ms 8244 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 314 ms 8148 KB Output is correct
5 Correct 264 ms 8276 KB Output is correct
6 Correct 456 ms 8160 KB Output is correct
7 Correct 342 ms 8412 KB Output is correct
8 Correct 252 ms 8264 KB Output is correct
9 Correct 449 ms 8420 KB Output is correct
10 Correct 161 ms 8208 KB Output is correct
11 Correct 149 ms 8248 KB Output is correct
12 Correct 134 ms 8276 KB Output is correct
13 Correct 362 ms 8268 KB Output is correct
14 Correct 166 ms 8244 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Execution timed out 1091 ms 19644 KB Time limit exceeded
18 Halted 0 ms 0 KB -