Submission #1098895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098895		NDT134	Stranded Far From Home (BOI22_island)	C++14	0 / 100	203 ms	28012 KiB

island

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
using pi = pair<int, int>;

vector<int> p, l, sm;
vector<vector<int>> w;

void find(int a)
{
	vector<int> v;
	while (p[a] != a)
	{
		v.push_back(a);
		a = p[a];
	}
	for (int x : v)
	{
		p[x] = a;
	}
}

int main() {
	int n, M; cin >> n >> M;
	sm.resize(n); p.resize(n); l.resize(n); w.resize(n);
	vector<vector<int>> g(n);
	vector<int> s(n);
	vector<pi> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
		p[i] = i; l[i] = 1; w[i].push_back(i); sm[i] = s[i];
		v[i] = { s[i],i };
	}
	for (int i = 0; i < M; i++)
	{
		int a, b; cin >> a >> b; a--; b--;
		g[a].push_back(b); g[b].push_back(a);
	}

	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++)
	{
		int x = v[i].second;
		bool b = 1;
		map<int, int> m;
		vector<int> a;
		for (int y : g[x])
		{
			if (s[y] < s[x] || (s[y] == s[x] && y < x))
			{
				find(y);
				if (!m[p[y]])
				{
					m[p[y]] = 1;
					a.push_back(p[y]);
				}
			}
		}
		if (!a.empty())
		{
			int j = a[0], k = l[a[0]];
			for (int y : a)
			{
				if (l[y] > k)
				{
					j = y; k = l[y];
				}
			}

			if (sm[j] < s[x])
			{
				w[j].clear();
			}
			w[j].push_back(x); l[j]++; sm[j] += s[x];
			for (int y : a)
			{
				if (y != j)
				{
					l[j] += l[y]; sm[j] += sm[y];
					if (sm[y] >= s[x])
					{
						for (int z : w[y])
						{
							w[j].push_back(z);
						}
					}
				}
			}

			for (int y : a)
			{
				p[y] = j;
			}
			p[x] = j;
		}
	}

	vector<int> r(n);
	for (int i = 0; i < n; i++)
	{
		if (p[i] == i)
		{
			for (int y : w[i])
			{
				r[y] = 1;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << r[i];
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:47:8: warning: unused variable 'b' [-Wunused-variable]
   47 |   bool b = 1;
      |        ^

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