Submission #603243

#	Time	Username	Problem	Language	Result	Execution time	Memory
603243		CSQ31	Stranded Far From Home (BOI22_island)	C++17	100 / 100	178 ms	30804 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
const int MAXN = 2e5+5;
int s[MAXN],par[MAXN];
ll sum[MAXN];
vector<int>adj[MAXN],g[MAXN];
bool good[MAXN];
int find(int x){
	if(x==par[x])return x;
	return par[x] = find(par[x]);
	
}
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>s[i];
	vector<array<int,3>>e;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		if(s[a] > s[b])swap(a,b);
		e.pb({s[b],a,b});
	}
	for(int i=0;i<n;i++){
		par[i] = i;
		sum[i] = s[i];
		good[i] = 1;
		g[i].pb(i);
	}
	sort(all(e));
	for(auto x:e){
		int v = x[1];
		int u = x[2];
		if(find(v) == find(u))continue;
		if(sum[par[v]] < s[u]){
			for(int x:g[par[v]])good[x] = 0;
			g[par[v]].clear();
		}
		v = find(v);
		u = find(u);
		if(sz(g[v]) > sz(g[u]))swap(v,u);
		sum[u]+=sum[v];
		for(int x:g[v])g[u].pb(x);
		par[v] = u;
	}
	for(int i=0;i<n;i++)cout<<good[i];
	
}

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