Submission #668158

#	Time	Username	Problem	Language	Result	Execution time	Memory
668158		Sohsoh84	Stranded Far From Home (BOI22_island)	C++17	100 / 100	488 ms	183620 KiB

island

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll LOG = 20;
const ll INF = 2e18;

// use sz instead of n :/
ll P[MAXN], n, m, F[MAXN], sz, val[MAXN], 
    par[MAXN][LOG], W[MAXN][LOG], S[MAXN];
vector<int> C[MAXN];
vector<pair<int, pll>> edges;

inline bool unite(int u, int v, int w) {
	u = P[u], v = P[v];
	if (u == v) return false;
	if (C[u].size() < C[v].size()) swap(u, v);

	sz++;
	par[F[u]][0] = par[F[v]][0] = sz;
	W[F[u]][0] = W[F[v]][0] = w;
	S[sz] = S[F[u]] + S[F[v]];

	F[u] = sz;
	for (int e : C[v]) {
		P[e] = u;
		C[u].push_back(e);
	}

	C[v].clear();
	return true;
}

inline int try_up(int v, ll val) {
	for (int i = LOG - 1; i >= 0; i--)
		if (W[v][i] <= val)
			v = par[v][i];

	return v;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
		C[i] = {i};
		P[i] = F[i] = i;
		S[i] = val[i];
		sz++;
	}

	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		edges.push_back({int(max(val[v], val[u])), {u, v}});
	}

	sort(all(edges));
	for (auto [w, e] : edges)
		unite(e.X, e.Y, w);

	fill(W[0], W[0] + LOG, INF);
	W[sz][0] = INF;
	for (int i = 1; i < LOG; i++) {
		for (int v = 1; v <= sz; v++) {
			int p = par[v][i - 1];
			par[v][i] = par[p][i - 1];
			W[v][i] = W[p][i - 1];
		}
	}

	for (int i = 1; i <= n; i++) {
		int v = i;
		while (W[v][0] <= S[v])
			v = try_up(v, S[v]);

		cout << (v == sz ? 1 : 0);
	}

	cout << endl;
	return 0;
}

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