Submission #1179593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179593		tamyte	Stranded Far From Home (BOI22_island)	C++20	100 / 100	123 ms	31576 KiB

island

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>> lefty;
struct DSU {
	vector<int> e;
	vector<ll> sum;
	DSU(int n) {
		e = vector<int>(n, -1);
		sum = vector<ll>(n);
	}
	int get(int x) {
		return e[x] < 0 ? x : e[x] = get(e[x]);
	}
	void unite(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return;
		if (lefty[x].size() < lefty[y].size()) swap(x, y);
		e[x] += e[y];
		sum[x] += sum[y];
		e[y] = x;
	}
};

void merge(int x, int y) {
	if (lefty[x].size() < lefty[y].size()) {
		swap(x, y);
	}
	lefty[x].insert(lefty[x].end(), 
                    make_move_iterator(lefty[y].begin()), 
                    make_move_iterator(lefty[y].end()));
    lefty[y].clear();
}


int main(){
    // random_device rd;
    // mt19937 rng(rd());
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 	int n, m;
 	cin >> n >> m;
 	vector<vector<int>> adj(n);
 	vector<int> v(n);
 	lefty = vector<vector<int>>(n);
 	for (int i = 0; i < n; ++i) {
 		lefty[i].push_back(i);
 	}
 	DSU dsu(n);
 	for (int i = 0; i < n; ++i) {
 		cin >> v[i];
 		dsu.sum[dsu.get(i)] += v[i];
 	}   
 	for (int i = 0; i < m; ++i) {
 		int a, b;
 		cin >> a >> b;
 		--a; --b;
 		adj[a].push_back(b);
 		adj[b].push_back(a);
 	}
 	vector<int> id(n);
 	iota(begin(id), end(id), 0);
 	sort(begin(id), end(id), [&](const int x, const int y) {
 		return v[x] < v[y];
 	});
 	vector<bool> open(n);
 	for (int i = 0; i < n;) {
 		int j = i;
 		int ii = id[i];
		// cout << "BEGIN: ";
 		for (int jj = id[j]; j < n && v[ii] == v[jj]; ++j, jj = id[j]) {
 			// cout << id[j] << " ";
 			open[jj] = true;
 		}
 		j = i;
 		// for (auto u : open) {
 			// cout << u << " ";
 		// }
 		// cout << endl;
 		for (int jj = id[j]; j < n && v[ii] == v[jj]; ++j, jj = id[j]) {
 			for (auto& u : adj[jj]) {
 				if (!open[u]) continue;
 				int v1 = dsu.get(jj);
 				int v2 = dsu.get(u);
 				if (v1 == v2) continue;
 				if (dsu.sum[v1] < v[u]) {
 					lefty[v1].clear();
 				}
 				if (dsu.sum[v2] < v[jj]) {
 					lefty[v2].clear();
 				}
 				// cout << "NOW: " << dsu.sum[v1] << " " << dsu.sum[v2] << endl;
 				merge(v1, v2);
 				if (dsu.sum[v2] >= v[jj] || dsu.sum[v1] >= v[u]) {
 					dsu.unite(v1, v2);
 				}
 			}
 		}
 		// cout << i << " " << j << endl;
 		i = j;
 	}
 	vector<int> res(n);
 	for (int i = 0; i < n; ++i) {
 		for (auto& u : lefty[i]) {
 			res[u] = 1;
 		}
 	}
 	for (auto& u : res) {
 		cout << u;
 	}
 	cout << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35