Submission #758986

#	Time	Username	Problem	Language	Result	Execution time	Memory
758986		ymm	Stranded Far From Home (BOI22_island)	C++17	100 / 100	249 ms	41128 KiB

island

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
vector<int> A0[N], A[N];
int val[N];
pii srt[N];
int n, m;

namespace dsu {
	int par[N];
	void init(int n) { fill(par, par+n, -1); }
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
}

ll sum[N];
void dfs_sum(int v)
{
	sum[v] = val[v];
	for (int u : A[v]) {
		dfs_sum(u);
		sum[v] += sum[u];
	}
}

bool ans[N];
void dfs_solve(int v, int pv)
{
	if (sum[v] < pv)
		return;
	ans[v] = 1;
	for (int u : A[v])
		dfs_solve(u, val[v]);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		cin >> val[i];
		srt[i] = {val[i], i};
	}
	sort(srt, srt+n);
	Loop (i,0,m) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A0[v].push_back(u);
		A0[u].push_back(v);
	}
	dsu::init(n);
	Loop (i,0,n) {
		int v = srt[i].second;
		for (int u : A0[v]) {
			if (val[v] < val[u])
				continue;
			if (dsu::rt(v) != dsu::rt(u)) {
				A[v].push_back(dsu::rt(u));
				dsu::unite(v, u);
			}
		}
	}
	dfs_sum(dsu::rt(0));
	dfs_solve(dsu::rt(0), -1);
	Loop (i,0,n)
		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