제출 #1129734

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

island

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define size(x) (int)(x).size()
#define int long long

typedef pair <int,int> pii;

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Dsu{
	vector <int> fa, cnt, ans;
	vector <vector<int>> c;
	
	Dsu(int n, vector <int> cnt) : fa(n), cnt(cnt), ans(n), c(n) {
		for ( int i = 0; i < n; i++ ){
			fa[i] = i; ans[i] = 1;
			c[i].pb(i);
		}
	}
	
	int get(int u){
		return fa[u] ^ u ? fa[u] = get(fa[u]) : u;
	}
	
	void set(int u){
		u = get(u);
		
		for ( auto &x: c[u] ) ans[x] = 0;
		c[u].clear();
	}
	
	void merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return;
		
		if ( size(c[u]) < size(c[v]) ) swap(u, v);
		
		fa[v] = u, cnt[u] += cnt[v];
		
		for ( auto &x: c[v] ) c[u].pb(x);
		c[v].clear();
	}
	
	int qry(int x){ return cnt[get(x)]; }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; cin >> n >> m;
    
    vector <int> s(n);
    
    for ( auto &u: s ) cin >> u;
    
    vector <ar<int,2>> e(m);
    
    for ( auto &[u, v]: e ){
		cin >> u >> v;
		
		--u, --v;
		
		if ( s[u] > s[v] ) swap(u, v);
	}
	
	sort(all(e), [&](auto &u, auto &v){
		return s[u[1]] < s[v[1]];
	});
	
	Dsu ds(n, s);
	
	for ( auto &[u, v]: e ){
		if ( ds.qry(u) < s[v] ) ds.set(u);
		
		ds.merge(u, v);
	}
	
	for ( auto &x: ds.ans ) cout << x; 

  	cout << '\n';
}

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