Submission #725617

#	Time	Username	Problem	Language	Result	Execution time	Memory
725617		WonderfulWhale	Stranded Far From Home (BOI22_island)	C++17	0 / 100	810 ms	136756 KiB

island

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

#define ll long long
#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;
vector<pair<int, pii>> edges;

int p[MAXN];
ll sum[MAXN];
multiset<pii> S[MAXN];
vector<int> cost;
vector<tuple<int, int, int, ll, vector<pii>>> undo_list;

void undo() {
	if(undo_list.empty()) return;
	auto &[y, old_p, x, old_sum, added_values] = undo_list.back();
	p[y] = old_p;
	sum[x] = old_sum;
	for(pii val:added_values) {
		S[x].erase(S[x].find(val));
	}
	undo_list.pop_back();
	cost.pop_back();
}

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

void Union(int x, int y, int c) {
	int X = Find(x);
	int Y = Find(y);
	if(X==Y) return;
	if(sz(S[X])<sz(S[Y])) swap(X, Y);
	undo_list.push_back({Y, p[Y], X, sum[X], {}});
	cost.pb(c);
	p[Y] = X;
	sum[X] += sum[Y];
	vector<pii> &added_values = get<4>(undo_list.back());
	for(pii val:S[Y]) {
		S[X].insert(val);
		added_values.pb(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.pb({max(tab[a], tab[b]), {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});
			}
		}
	}
	sort(all(edges));
	for(auto x:edges) {
		Union(x.nd.st, x.nd.nd, x.st);
	}
	for(int x:M[-Max]) {
		ans[x] = true;
	}
	M.erase(-Max);
	while(sz(cost)&&cost.back()==Max) undo();
	for(auto &x:M) {
		for(int y:x.nd) {
			int Y = Find(y);
			auto it = S[Y].upper_bound({sum[Y], 1e9});
			if(it!=S[Y].begin()) {
				it--;
				if(ans[it->nd]) {
					ans[y] = true;
				}
			}
		}
		while(sz(cost)&&cost.back()==-x.st) undo();
	}
	for(int i=1;i<=n;i++) {
		cout << ans[i];
	}
	cout << "\n";
}

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