oj.uz

Submission #711057

# Submission time Handle Problem Language Result Execution time Memory
711057 2023-03-16T07:51:34 Z blackscreen1 Stranded Far From Home (BOI22_island) C++17
0 / 100
 155 ms 22020 KB 
#include <bits//stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i+=(m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j+=(m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k+=(m<h?1:-1))
#define lloop(m, h) for (auto l = m; l != h; l+=(m<h?1:-1))
#define iloop_(m, h, g) for (auto i = m; i != h; i+=g)
#define jloop_(m, h, g) for (auto j = m; j != h; j+=g)
#define kloop_(m, h, g) for (auto k = m; k != h; k+=g)
#define lloop_(m, h, g) for (auto l = m; l != h; l+=g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll,ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll par[200005], n, m;
bool active[200005];
ll tot[200005], mi[200005];
ll a[200005];
pll b[200005];
vll adj[200005];
ll t1, t2;
ll find(ll x) {
	return (par[x] == x ? x : par[x] = find(par[x]));
}
void merge(ll x, ll y) {
	x = find(x);
	y = find(y);
	//cout << x << " " << y << "\n";
	if (x == y) return;
	if (tot[y] < mi[x] || tot[x] < mi[y]) return;
	//cout << "e\n";
	tot[x] += tot[y];
	mi[x] = min(mi[x], mi[y]);
	par[y] = x;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    iloop(0, n+1) {
		par[i] = i;
	}
    iloop(1, n+1) {
		cin >> a[i];
		b[i] = {a[i], i};
		tot[i] = mi[i] = a[i];
	}
	iloop(0, m) {
		cin >> t1 >> t2;
		adj[t1].push_back(t2);
		adj[t2].push_back(t1);
	}
	sort(b+1, b+n+1);
	iloop(1, n+1) {
		//cout << b[i].second << "\n";
		active[b[i].second] = 1;
		for (auto it : adj[b[i].second]) {
			if (active[it] && tot[find(it)] >= b[i].first) merge(b[i].second, it);
		}
	}
	iloop(1, n+1) {
		if (find(i) == find(b[n].second)) cout << 1;
		else cout << 0;
	}
}

Subtask #1
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 2 ms 4948 KB Output is correct
4 Incorrect 4 ms 5204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Incorrect 115 ms 22012 KB Output isn't correct
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 Incorrect 148 ms 20896 KB Output isn't correct
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 Incorrect 155 ms 22020 KB Output isn't correct
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 2 ms 4948 KB Output is correct
4 Incorrect 4 ms 5204 KB Output isn't correct
5 Halted 0 ms 0 KB -