Submission #587363

#	Time	Username	Problem	Language	Result	Execution time	Memory
587363		blue	Stranded Far From Home (BOI22_island)	C++17	100 / 100	369 ms	44248 KiB

island

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using ll = long long;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using vvll = vector<vll>;
using namespace std;

const int mx = 200'000;

int N, M;
vll s(1+mx);
vi sn(1+mx);
vi edge[1+mx];

vi children[1+mx];

struct dsu
{
	vi parent = vi(1+mx);
	vi subtree = vi(1+mx);
	vi peak = vi(1+mx);

	dsu()
	{
		for(int i = 1; i <= N; i++)
		{
			parent[i] = peak[i] = i;
			subtree[i] = 1;
		}
	}

	int root(int u)
	{
		if(parent[u] == u)
			return u;
		else
			return (parent[u] = root(parent[u]));
	}

	bool join(int u, int v)
	{
		u = root(u);
		v = root(v);

		if(u == v) return 0;

		if(subtree[u] < subtree[v])
			swap(u, v);

		subtree[u] += subtree[v];
		parent[v] = u;
		peak[u] = sn[peak[u]] < sn[peak[v]] ? peak[v] : peak[u];
		return 1;
	}
};

string res;

int rt;
vll ssum;


void dfs(int u)
{
	res[u-1] = '1';
	for(int v : children[u])
	{
		if(ssum[v] >= s[u])
			dfs(v);
	}
}

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

	cin >> N >> M;
	for(int i = 1; i <= N; i++)
		cin >> s[i];

	for(int e = 1; e <= M; e++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	vi ord;
	for(int i = 1; i <= N; i++)
		ord.push_back(i);

	sort(ord.begin(), ord.end(), [] (int u, int v)
	{
		return s[u] < s[v];
	});

	for(int i = 0; i < N; i++)
		sn[ord[i]] = i;

	vi parent(1+N);

	ssum = s;


	dsu DSU;

	for(int u : ord)
	{
		for(int v : edge[u])
		{
			if(sn[v] > sn[u]) continue;

			if(DSU.root(u) == DSU.root(v)) continue;

			int vp = DSU.peak[DSU.root(v)];

			ssum[u] += ssum[vp];

			parent[vp] = u;
			children[u].push_back(vp);

			DSU.join(u, vp);
		}
	}

	// for(int u : ord)
	// 	cerr << u << ' ';
	// cerr << '\n';

	// for(int u = 1; u <= N; u++)
	// {
	// 	cerr << "\n\n\n";
	// 	cerr << "u = " << u << " : " << ssum[u] << '\n';
	// 	for(int v : children[u])
	// 		cerr << u << " -> " << v << '\n';
	// }

	res = string(N, '0');

	rt = ord.back();
	dfs(rt);

	cout << res << '\n';
}

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