oj.uz

Submission #587078

# Submission time Handle Problem Language Result Execution time Memory
587078 2022-07-01T09:40:41 Z fuad27 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 23280 KB 
/*
 * Created: 2022-07-01 13:35
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll inf = 1e18;

#define pii		pair<int,int>
#define pll		pair<ll,ll>
#define vi		vector<int>
#define vll		vector<ll>
#define rep(i, a, b)	for(int i = (a);i<(b);i++)
#define repn(i, a, b)	for(int i = (a);i>=(b);i--)
#define ss		second
#define ff		first
#define mkp		make_pair
#define pb		push_back

#define all(x)		(x).begin(), (x).end()
const int N = 200'010;
vll g[N];
ll s[N];
void solve() {
	int n, m;
	cin >> n >> m;
	rep(i, 0, n) {
		cin >> s[i];
	}
	rep(i, 0, m) {
		int a, b;
		cin >> a >> b;
		a--,b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	for(int i = 0;i<n;i++) {
		multiset<pll> ms;
		vector<bool> vis(n);
		ms.insert(mkp(0,i));
		long long sum = 0;
		bool check=1;
		while(ms.size()) {
			int at = (*ms.begin()).second;
			ms.erase(ms.begin());
			if(vis[at])continue;
			vis[at]=1;
			if(sum == 0) {
				sum+=s[at];
			}
			else if(sum < s[at])check=0;
			else sum+=s[at];
			for(int to:g[at]) {
				ms.insert(mkp(s[to], to));
			}
		}
		cout<<check;
	}
	cout<<"\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while(t--) {
		solve();
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 676 ms 5124 KB Output is correct
5 Correct 643 ms 5124 KB Output is correct
6 Correct 640 ms 5124 KB Output is correct
7 Correct 634 ms 5136 KB Output is correct
8 Correct 484 ms 5104 KB Output is correct
9 Correct 599 ms 5224 KB Output is correct
10 Correct 487 ms 5084 KB Output is correct
11 Correct 476 ms 5092 KB Output is correct
12 Correct 481 ms 5108 KB Output is correct
13 Correct 541 ms 5204 KB Output is correct
14 Correct 698 ms 5096 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 5020 KB Output is correct
3 Execution timed out 1018 ms 23280 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 1050 ms 14848 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 1022 ms 16100 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 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 676 ms 5124 KB Output is correct
5 Correct 643 ms 5124 KB Output is correct
6 Correct 640 ms 5124 KB Output is correct
7 Correct 634 ms 5136 KB Output is correct
8 Correct 484 ms 5104 KB Output is correct
9 Correct 599 ms 5224 KB Output is correct
10 Correct 487 ms 5084 KB Output is correct
11 Correct 476 ms 5092 KB Output is correct
12 Correct 481 ms 5108 KB Output is correct
13 Correct 541 ms 5204 KB Output is correct
14 Correct 698 ms 5096 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5020 KB Output is correct
17 Execution timed out 1018 ms 23280 KB Time limit exceeded
18 Halted 0 ms 0 KB -