Submission #790886

#	Time	Username	Problem	Language	Result	Execution time	Memory
790886		esomer	Stranded Far From Home (BOI22_island)	C++17	100 / 100	165 ms	24368 KiB

island

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU{
	vector<int> v;
	vector<ll> sum;
	vector<ll> ans;
	vector<int> lst;
	
	void init(vector<pair<int, int>>& a){
		int n = (int)a.size();
		v.assign(n, -1);
		sum.assign(n, 0);
		ans.resize(n);
		lst.resize(n);
		for(int i = 0; i < n; i++){
			sum[a[i].second] = a[i].first;
			ans[a[i].second] = a[i].first;
			lst[a[i].second] = a[i].second;
		}
	}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	
	void unite(int x, int y, pair<int, int> val){
		x = get(x); y = get(y);
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		if(lst[x] != val.second && sum[x] >= val.first) ans[lst[x]] = -val.second;
		if(lst[y] != val.second && sum[y] >= val.first) ans[lst[y]] = -val.second;
		v[x] += v[y]; v[y] = x;	sum[x] += sum[y];
		lst[x] = val.second;
		ans[val.second] = sum[x];
	}
};

void solve(){
	int n, m; cin >> n >> m;
	vector<pair<int, int>> v(n);
	ll total_sum = 0;
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		total_sum += x;
		v[i] = {x, i};
	}
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b; a--; b--;
		adj[a].push_back({v[b].first, b});
		adj[b].push_back({v[a].first, a});
	}
	sort(v.begin(), v.end());
	DSU UF; UF.init(v);
	for(int i = 0; i < n; i++){
		for(pair<int, int> p : adj[v[i].second]){
			if(p > v[i]) continue;
			UF.unite(v[i].second, p.second, v[i]);
		}
	}
	for(int j = n - 1; j >= 0; j--){
		int i = v[j].second;
		if(UF.ans[i] <= 0) UF.ans[i] = UF.ans[-UF.ans[i]];
	}
	for(ll x : UF.ans) cout << (x == total_sum ? 1 : 0);
	cout << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	solve();
}

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