제출 #1227643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227643		altern23	Stranded Far From Home (BOI22_island)	C++20	100 / 100	556 ms	35528 KiB

island

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 1e18;
const int MOD = 998244353;

ll a[MAXN + 5], act[MAXN + 5], sum[MAXN + 5];
vector<ll> adj[MAXN + 5];

struct DSU{
	ll N;
	vector<ll> par;
	vector<set<ll>> ans;
	DSU(ll _n){
		N = _n;
		par.resize(N + 5);
		ans = vector<set<ll>> (N + 5);
		for(int i = 1; i <= N; i++){
			par[i] = i;
			ans[i].insert(i);
		}
	}
	ll find(ll idx){
		return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
	}
	bool join(ll a, ll b, ll weight){
		a = find(a), b = find(b);
		if(a == b) return false;
		// gabisa makan
		if(sum[a] < weight){
			ans[a].clear();
		}
		if(sum[b] < weight){
			ans[b].clear();
		}
		
		if(ans[b].size() > ans[a].size()){
			swap(a, b);
		}
		sum[a] += sum[b];
		par[b] = a;
		for(auto &i : ans[b]){
			ans[a].insert(i);
		}
		ans[b].clear();
		return true;
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M; cin >> N >> M;
		for(int i = 1; i <= N; i++){
			cin >> a[i];
			sum[i] = a[i];
		}
		vector<pair<ll, pii>> edges;
		for(int i = 1; i <= M; i++){
			ll u, v; cin >> u >> v;
			edges.push_back({max(a[u], a[v]), {u, v}});
		}
		
		sort(edges.begin(), edges.end());
		
		DSU dsu(N);
		for(auto [weight, cur] : edges){
			dsu.join(cur.fi, cur.sec, weight);
		}
		
		for(int i = 1; i <= N; i++){
			ll get = dsu.find(i);
			cout << bool(dsu.ans[get].find(i) != dsu.ans[get].end());
		}
		cout << "\n";
	}	
}

/*

*/

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