oj.uz

Submission #711106

# Submission time Handle Problem Language Result Execution time Memory
711106 2023-03-16T08:39:47 Z WH8 Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 19924 KB 
#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lll pair<int, pair<int, int>>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

int p[200005];
int gz[200005];

vector<int> bfs[200005];

int par(int x){
	if (p[x] == x) return x;
	return p[x] = par(p[x]);
}

void merge(int a, int b){
	int x = par(a), y = par(b);
	if (x == y) return;
	if (gz[x] < gz[y]){
		p[x] = y;
	}
	else {
		p[y] = x;
	}
}

int32_t main(){
	FASTIO
	int n, m; cin >> n >> m;
	vector<vi> al(n+1);
	vector<int> v(n); iloop(0, n) {
		int c;
		cin >> c;
		v[i] = c;
	}
	iloop(0, m){
		int a, b; cin >> a >> b;
		a--; b--;
		al[a].pb(b); al[b].pb(a);
	}
	bool ans[n]; iloop(0, n) ans[i] = 0;
	iloop(0, n){
		//cout << endl << i << endl;
		priority_queue<pll, vector<pll>, greater<pll>> pq;
		bool vis[n];
		bool fail = 0;
		iloop(0, n) vis[i] = 0;
		vis[i] = true;
		pq.emplace(0, i);
		int p = v[i];
		while (!pq.empty()){
			int gain = pq.top().f, cur = pq.top().s; pq.pop();
			//debug(cur);
			if (gain > p) {
				fail = 1;
				break;
			}
			p += gain;
			for (auto it : al[cur]){
				if (vis[it]) continue;
				vis[it] = true;
				pq.emplace(v[it], it);
			}
		}
		if (fail){
			ans[i] = 0;
		}
		else ans[i] = 1;
	}
	iloop(0, n) cout << ans[i];
}

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 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 156 ms 5148 KB Output is correct
5 Correct 151 ms 5188 KB Output is correct
6 Correct 200 ms 5172 KB Output is correct
7 Correct 158 ms 5076 KB Output is correct
8 Correct 118 ms 5160 KB Output is correct
9 Correct 221 ms 5208 KB Output is correct
10 Correct 54 ms 5180 KB Output is correct
11 Correct 44 ms 5184 KB Output is correct
12 Correct 62 ms 5196 KB Output is correct
13 Correct 83 ms 5076 KB Output is correct
14 Correct 92 ms 5172 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 1087 ms 19924 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 4956 KB Output is correct
2 Execution timed out 1058 ms 17868 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 1083 ms 19268 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 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 156 ms 5148 KB Output is correct
5 Correct 151 ms 5188 KB Output is correct
6 Correct 200 ms 5172 KB Output is correct
7 Correct 158 ms 5076 KB Output is correct
8 Correct 118 ms 5160 KB Output is correct
9 Correct 221 ms 5208 KB Output is correct
10 Correct 54 ms 5180 KB Output is correct
11 Correct 44 ms 5184 KB Output is correct
12 Correct 62 ms 5196 KB Output is correct
13 Correct 83 ms 5076 KB Output is correct
14 Correct 92 ms 5172 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 1087 ms 19924 KB Time limit exceeded
18 Halted 0 ms 0 KB -