Submission #1130462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130462		Acanikolic	Stranded Far From Home (BOI22_island)	C++20	100 / 100	165 ms	33624 KiB

island

#include <bits/stdc++.h>

#define int long long

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 2e5 + 10;

const int mod = 1e9 + 7;

const int inf = 2e18;
 
vector<int>g[N]; 
vector<array<int,3>>edges;
int par[N],mx[N],sum[N],ans[N];

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

void unite(int u,int v) {
	u = get(u);
	v = get(v);
	if(u == v) return;
	if(sum[u] < mx[v]) g[u].clear();
	if(sum[v] < mx[u]) g[v].clear();
	if(g[u].size() > g[v].size()) swap(u,v);
	for(int j : g[u]) g[v].pb(j);
	g[u].clear();
	par[u] = v;
	sum[v] += sum[u];
	mx[v] = max(mx[v],mx[u]);	
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

 	int n,m;
 	cin >> n >> m;
 	vector<int>a(n + 1);
 	for(int i = 1; i <= n; i++) cin >> a[i];
 	for(int i = 1; i <= m; i++) {
 		int u,v;
 		cin >> u >> v;
 		edges.pb({max(a[u],a[v]),u,v});
 	}
 	sort(edges.begin(),edges.end());
 	for(int i = 1; i <= n; i++) {
 		g[i] = {i};
 		par[i] = i;
 		sum[i] = a[i];
 		mx[i] = a[i];
 	}
 	for(auto X : edges) unite(X[1],X[2]);
 	for(int j : g[get(1)]) ans[j] = 1;
 	for(int i = 1; i <= n; i++) cout << ans[i];
    return 0;
}

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