oj.uz

Submission #591146

# Submission time Handle Problem Language Result Execution time Memory
591146 2022-07-06T23:02:03 Z tutis Stranded Far From Home (BOI22_island) C++17
0 / 100
 202 ms 25532 KB 
/*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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 138 ms 25172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 195 ms 25532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 202 ms 25368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -