Submission #725626

#	Time	Username	Problem	Language	Result	Execution time	Memory
725626		WonderfulWhale	Stranded Far From Home (BOI22_island)	C++17	100 / 100	976 ms	141420 KiB

island

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

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int MAXN = 200009;

int tab[MAXN];
vector<int> G[MAXN];
bool ans[MAXN];
map<int, vector<int>> M;
map<int, vector<pii>> edges;
int dependency[MAXN];

int p[MAXN];
int sum[MAXN];
multiset<pii> S[MAXN];
vector<int> cost;

int Find(int x) {
	return p[x]==x?x:p[x]=Find(p[x]);
}

void Union(int x, int y) {
	int X = Find(x);
	int Y = Find(y);
	if(X==Y) return;
	if(sz(S[X])<sz(S[Y])) swap(X, Y);
	p[Y] = X;
	sum[X] += sum[Y];
	sum[X] = min(sum[X], 1000000009);
	for(pii val:S[Y]) {
		S[X].insert(val);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	int Max = 0;
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
		M[tab[i]].pb(i);
		Max = max(Max, tab[i]);
	}
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
		edges[max(tab[a], tab[b])].pb({a, b});
	}
	for(int i=1;i<=n;i++) {
		p[i] = i;
		sum[i] = tab[i];
		for(int x:G[i]) {
			if(tab[x]>tab[i]) {
				S[i].insert({tab[x], x});
			}
		}
	}
	for(auto &x:M) {
		for(pii y:edges[x.st]) {
			Union(y.st, y.nd);
		}
		for(int y:x.nd) {
			int Y = Find(y);
			auto it = S[Y].upper_bound({sum[Y], 1e9});
			if(it!=S[Y].begin()) {
				it--;
				dependency[y] = it->nd;
			}
		}
	}
	for(int x:M[Max]) {
		ans[x] = true;
	}
	M.erase(Max);
	for(auto it = M.rbegin();it!=M.rend();it++) {
		for(int y:(*it).nd) {
			if(ans[dependency[y]]) {
				ans[y] = true;
			}
		}
	}
	for(int i=1;i<=n;i++) {
		cout << ans[i];
	}
	cout << "\n";
}

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