Submission #711697

#	Time	Username	Problem	Language	Result	Execution time	Memory
711697		hpesoj	Stranded Far From Home (BOI22_island)	C++17	100 / 100	283 ms	43792 KiB

island

#include <bits/stdc++.h>
#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
#define debug4(x, y, z, w) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << ' ' << #w << ": " << w << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

const int inf = 1000000000000000000, mod = 998244353;
int n, m, root[200005], val[200005];
pi s[200005];
vector <int> nodes[200005];
vector <int> adj[200005];
bool processed[200005], ans[200005];
int getroot(int x){
	if(x == root[x]) return x;
	else return root[x] = getroot(root[x]);
}
void merge(int x, int y){
	int rootx = getroot(x), rooty = getroot(y);
	//debug4(x, rootx, y, rooty);
	if(rootx == rooty) return;
	if(nodes[rootx].size() < nodes[rooty].size()) swap(rootx, rooty);
	root[rooty] = rootx, val[rootx] += val[rooty];
	for(auto it = nodes[rooty].begin(); it != nodes[rooty].end(); it++) nodes[rootx].pb(*it);
	nodes[rooty].clear();
	//cout << "merged: " << x << ", " << y << '\n';
}
void mark(int x){
	for(auto it = nodes[x].begin(); it != nodes[x].end(); it++) ans[*it] = 0;
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	fill(ans+1, ans+n+1, 0);
	for(int i = 1; i <= n; i++){
		cin >> s[i].fi;
		s[i].se = i, root[i] = i, val[i] = s[i].fi;
		nodes[i].pb(i);
	}
	for(int i = 1; i <= m; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	sort(s+1, s+n+1);
	for(int i = 1; i <= n; i++){
		processed[s[i].se] = 1;
		for(int j : adj[s[i].se]){
			//debug3(s[i].se, j, processed[j]);
			if(!processed[j]) continue;
			int k = getroot(j);
			//debug4(s[i].se, s[i].fi, k, val[k]);
			if(s[i].fi > val[k]){
				nodes[k].clear();
			}
			merge(s[i].se, k);
		}
	}
	for(int i = 1; i <= n; i++){
		if(i != getroot(i)) continue;
		for(auto it = nodes[i].begin(); it != nodes[i].end(); it++) ans[*it] = 1;
	}
	for(int i = 1; i <= n; i++) cout << ans[i];
}
	

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