Submission #710909

#	Time	Username	Problem	Language	Result	Execution time	Memory
710909		penguin133	Stranded Far From Home (BOI22_island)	C++17	100 / 100	296 ms	48448 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, A[300005], par[300005], sz[300005];
vector <int> stuf[300005], adj[300005];
pi B[300005];
bool ans[300005];

int getr(int x){
	return (par[x] == x ? x : par[x] = getr(par[x]));
}

void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a == b)return;
	if(stuf[a].size() < stuf[b].size())swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
	for(auto i : stuf[b])stuf[a].push_back(i);
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> A[i];
	while(m--){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++)par[i] = i, B[i] = {A[i], i};
	sort(B+1, B+n+1);
	for(int i=1;i<=n;i++){
		sz[B[i].se] = B[i].fi;
		stuf[B[i].se].push_back(B[i].se);
		for(auto j : adj[B[i].se]){
			if(sz[getr(j)]){
				int x = getr(j);
				if(sz[x] < B[i].fi){
					stuf[x].clear();
				}
				merge(x, B[i].se);
			}
		}
	}
	set <int> s;
	for(int i=1;i<=n;i++){
		if(s.find(getr(i)) != s.end())continue;
		s.insert(getr(i));
		for(auto j : stuf[getr(i)])ans[j] = 1;
	}
	for(int i=1;i<=n;i++)cout << ans[i];
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

island.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main(){
      | ^~~~

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