제출 #975091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975091		c2zi6	Stranded Far From Home (BOI22_island)	C++14	100 / 100	214 ms	53308 KiB

island

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

VI par, cnt;
VL sumc;
int get(int u) {
	return par[u] = (u == par[u] ? u : get(par[u]));
}
void join(int u, int v) {
	u = get(u);
	v = get(v);
	if (u == v) return;
	if (cnt[u] < cnt[v]) swap(u, v);
	par[v] = u;
	cnt[u] += cnt[v];
	sumc[u] += sumc[v];
}

VI s;

VVI tr;
VI ans;
VL sum;
void dfs(int u, int p = -1) {
	ans[u] = true;
	if (p != -1 && s[p] > sum[u]) ans[u] = false;
	if (p != -1 && ans[p] == false) ans[u] = false;
	for (int v : tr[u]) dfs(v, u);
}

void solve() {
	int n, m;
	cin >> n >> m;
	s = VI(n);
	for (int& x : s) cin >> x;
	VVI gp(n);
	rep(i, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		gp[u].pb(v);
		gp[v].pb(u);
	}
	VI ord;
	rep(u, n) ord.pb(u);
	sort(all(ord), [&](int a, int b){return s[a] < s[b];});
	VVI order;
	rep(i, n) {
		if (i == 0 || s[ord[i]] != s[ord[i-1]]) order.pb(VI());
		order.back().pb(ord[i]);
	}
	par = cnt = VI(n, 1);
	sumc = VL(n);
	rep(i, n) {
		par[i] = i;
		sumc[i] = s[i];
	}
	sum = VL(n);	// for one node
	VI mx(n);   // for one component
	rep(i, n) {
		sum[i] = s[i];
		mx[i] = i;
	}
	tr = VVI(n);
	for (VI ord : order) {
		for (int u : ord) for (int v : gp[u]) if (s[v] <= s[u]) if (get(u) != get(v)) {
			tr[u].pb(mx[get(v)]);
			int m = mx[get(u)];
			join(u, v);
			mx[get(u)] = m;
		}
		for (int u : ord) sum[u] = sumc[get(u)];
	}
	ans = VI(n, -1);
	dfs(mx[get(0)]);
	for (int x : ans) if (x == -1) {
		ans = VI(n, 0);
		break;
	}
	for (int x : ans) cout << x;
	cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /* cin >> t; */
    while (t--) solve();
}

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