Submission #590314

#	Time	Username	Problem	Language	Result	Execution time	Memory
590314		penguinhacker	Stranded Far From Home (BOI22_island)	C++17	100 / 100	582 ms	68148 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, m, s[mxN], p[mxN];
vector<int> adj[mxN], rts, tree[mxN];
map<int, vector<int>> mp;
bool ans[mxN];
set<ar<int, 2>> bigger[mxN];
ll sum[mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

void mrg(int u, int v) {
	if ((u=find(u))==(v=find(v)))
		return;
	if (s[u]<s[v])
		swap(u, v);
	p[v]=u;
	sum[u]+=sum[v];
	if (bigger[u].size()<bigger[v].size())
		swap(bigger[u], bigger[v]);
	for (ar<int, 2> i : bigger[v])
		bigger[u].insert(i);
	set<ar<int, 2>>().swap(bigger[v]);
	while(bigger[u].size()&&(*bigger[u].begin())[0]<=s[u]) {
		assert((*bigger[u].begin())[0]==s[u]);
		bigger[u].erase(bigger[u].begin());
	}
}

void dfs(int u) {
	ans[u]=1;
	for (int v : tree[u])
		dfs(v);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; ++i) {
		cin >> s[i];
		mp[s[i]].push_back(i);
		p[i]=i, sum[i]=s[i];
	}
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		if (s[v]>s[u])
			bigger[u].insert({s[v], v});
		if (s[u]>s[v])
			bigger[v].insert({s[u], u});
	}
	for (int x : mp.rbegin()->second)
		rts.push_back(x);
	for (auto it=mp.begin(); it!=mp.end(); ++it) {
		vector<int> nodes=it->second;
		for (int u : nodes)
			for (int v : adj[u])
				if (s[v]<=s[u])
					mrg(u, v);
		for (int u : nodes) {
			int v=find(u);
			if (bigger[v].size()&&sum[v]>=(*bigger[v].begin())[0])
				tree[(*bigger[v].begin())[1]].push_back(u);
		}
	}
	for (int i : rts)
		dfs(i);
	for (int i=0; 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