Submission #790494

#	Time	Username	Problem	Language	Result	Execution time	Memory
790494		esomer	Stranded Far From Home (BOI22_island)	C++17	0 / 100	277 ms	46064 KiB

island

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU{
	vector<int> v;
	vector<ll> sum;
	vector<set<pair<int, int>>> adj;
	
	void init(vector<pair<int, int>>& a, vector<vector<pair<int, int>>>& adj1){
		int n = (int)a.size();
		v.assign(n, -1);
		sum.assign(n, 0);
		adj.assign(n, {});
		for(int i = 0; i < n; i++){
			sum[a[i].second] = a[i].first;
			for(pair<int, int> p : adj1[a[i].second]){
				adj[a[i].second].insert(p);
			}
		}
	}
	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);
		while((int)adj[x].size() > 0 && *adj[x].begin() <= val) adj[x].erase(adj[x].begin());
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;	sum[x] += sum[y];
		if(adj[x].size() < adj[y].size()) swap(adj[x], adj[y]);
		for(pair<int, int> p : adj[y]) adj[x].insert(p);
		while((int)adj[x].size() > 0 && *adj[x].begin() <= val) adj[x].erase(adj[x].begin());
	}
	
	ll calc(int i){
		i = get(i);
		if((int)adj[i].size() == 0) return sum[i];
		else if(sum[i] >= (*adj[i].begin()).first) return -(*adj[i].begin()).second;
		else return sum[i];
	}
};

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});
	}
	vector<ll> ans(n);
	sort(v.begin(), v.end());
	DSU UF; UF.init(v, adj);
	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]);
		}
		ans[v[i].second] = UF.calc(v[i].second);
	}
	for(int j = n - 1; j >= 0; j--){
		int i = v[j].second;
		if(ans[i] <= 0) ans[i] = ans[-ans[i]];
	}
	for(int x : ans) cout << (x == total_sum ? 1 : 0);
	cout << endl;
}

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

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