Submission #967636

#	Time	Username	Problem	Language	Result	Execution time	Memory
967636		dong_gas	Stranded Far From Home (BOI22_island)	C++17	100 / 100	136 ms	30396 KiB

island

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
int n, m, a[200020];
vector<int> adj[200020], can[200020];
bool visited[200020];
vector<tuple<int,int,int>> edges;
 
struct disjoin_set{
	int papa[200020], sz[200020];
	ll sum[200020];
	void init() {
		for(int i=1;i<=n;i++) sum[i]=a[i], sz[i]=1, papa[i]=-1, can[i].emplace_back(i);
	}
	int Find(int u) {
		if(papa[u]==-1) return u;
		return papa[u]=Find(papa[u]);
	}
	bool Union(int u,int v) {
		u=Find(u), v=Find(v);
		if(u==v) return false;
		if(sz[u]<sz[v]) swap(u,v);
		papa[v]=u;
		sz[u]+=sz[v];
		sum[u]+=sum[v];
		for(auto x: can[v]) can[u].emplace_back(x);
		return true;
	}
} djs;

 
void solve() {
    cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(m --> 0) {
		int u, v; cin>>u>>v;
		if(a[u]<a[v]) swap(u,v);
		edges.push_back({a[u],u,v});
	}
	sort(all(edges));
	djs.init();
	for(auto& [_, u, v]: edges) {
		if(djs.sum[djs.Find(v)]<a[u]) can[djs.Find(v)].clear();
		djs.Union(u,v);
	}
	for(int& x: can[djs.Find(1)]) visited[x]=1;
	for(int i=1;i<=n;i++) cout<<visited[i];	
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
} 

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