Submission #1305522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305522		coolboy19521	Stranded Far From Home (BOI22_island)	C++20	100 / 100	125 ms	31204 KiB

island

#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn=2e5+20;

vector<int> aj[mxn];
int s[mxn];

struct{
	long long val[mxn];
	int ar[mxn];
	vector<int>loc[mxn];
	void init(int n){
		fill_n(ar,n,-1);
		F0R(i,n)val[i]=s[i];
		F0R(i,n)loc[i].push_back(i);
	}
	int find(int u){
		if(ar[u]<0)return u;
		else return ar[u]=find(ar[u]);
	}
	void unite(int u,int v){
		v=find(v);
		if(s[u]>val[v])loc[v].clear();
		u=find(u);
		if(u==v)return;
		if(loc[u].size()<loc[v].size())swap(u,v);
		val[u]+=val[v],ar[u]+=ar[v],ar[v]=u;
		for(int i:loc[v])loc[u].push_back(i);
		loc[v].clear();
	}
}DSU;

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,m;cin>>n>>m;
	F0R(i,n)cin>>s[i];
	DSU.init(n);
	REP(m){
		int a,b;cin>>a>>b;
		a--,b--;
		if(s[a]<s[b])swap(a,b);
		aj[a].push_back(b);
	}
	vector<pair<int,int>>vp;
	F0R(i,n)vp.emplace_back(s[i],i);
	sort(begin(vp),end(vp));
	for(auto&pr:vp){
		int w=pr.first,u=pr.second;
		for(int v:aj[u])DSU.unite(u,v);
	}
	vector<int>ans;
	F0R(i,n){
		for(int j:DSU.loc[i])ans.push_back(j);
	}
	string s(n,'0');
	for(int i:ans)s[i]='1';
	cout<<s<<endl;
}

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