Submission #591146

#	Time	Username	Problem	Language	Result	Execution time	Memory
591146		tutis	Stranded Far From Home (BOI22_island)	C++17	0 / 100	202 ms	25532 KiB

island

/*input
4 4
2 2 4 3
1 2
1 3
2 3
3 4

*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
	ios_base::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	int S[N];
	for (int i = 0; i < N; i++)
		cin >> S[i];
	int pa[N];
	int sz[N];
	ll sum[N];
	for (int i = 0; i < N; i++)
	{
		pa[i] = i;
		sz[i] = 1;
		sum[i] += S[i];
	}
	vector<int>adj[N];
	while (M--)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int w[N];
	int p[N];
	int mx[N];
	for (int i = 0; i < N; i++)
	{
		p[i] = i;
		mx[i] = i;
	}
	vector<array<int, 2>>last[N];
	sort(p, p + N, [&](int a, int b) {return S[a] < S[b];});
	for (int i : p)
	{
		for (int j : adj[i])
		{
			if (S[j] <= S[i])
			{
				int a = i;
				int b = j;
				while (pa[a] != a)
					a = pa[a];
				while (pa[b] != b)
					b = pa[b];
				if (a == b)
					continue;
				if (sz[a] > sz[b])
					swap(a, b);
				sz[b] += sz[a];
				pa[a] = b;
				w[a] = S[i];
				sum[b] += sum[a];
				last[b].push_back({a, mx[b]});
				if (S[mx[b]] < S[mx[a]])
					mx[b] = mx[a];
			}
		}
	}
	function<int(int)>root = [&](int i)
	{
		while (i != pa[i])
			i = pa[i];
		return i;
	};
	vector<bool>ret(N, false);
	vector<int>ok;
	ok.push_back(mx[root(0)]);
	vector<bool> inq(N, false);
	inq[mx[root(0)]] = true;
	while (!ok.empty())
	{
		int v = root(ok.back());
		ok.pop_back();
		int val = S[mx[v]];
		queue<int>Q;
		Q.push(v);
		vector<int>maxiai;
		while (!Q.empty())
		{
			int b = Q.front();
			Q.pop();
			if (sz[b] == 1 && S[b] == val)
				ret[b] = 1;
			if (last[b].size() > 0)
			{
				int a = last[b].back()[0];
				if (w[a] == val)
				{
					mx[b] = last[b].back()[1];
					last[b].pop_back();
					pa[a] = a;
					sz[b] -= sz[a];
					sum[b] -= sum[a];
					Q.push(a);
					Q.push(b);
					if (mx[a] != val && sum[a] >= val)
					{
						if (inq[mx[a]] == true)
							ok.push_back(mx[a]);
					}
					if (mx[b] != val && sum[b] >= val)
					{
						if (inq[mx[b]] == false)
							ok.push_back(mx[b]);
					}
				}
			}
		}
	}
	for (int i : ret)
		cout << i;
	cout << "\n";
}

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