oj.uz

Submission #1098895

# Submission time Handle Problem Language Result Execution time Memory
1098895 2024-10-10T09:50:49 Z NDT134 Stranded Far From Home (BOI22_island) C++14
0 / 100
 203 ms 28012 KB 
#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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 604 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 180 ms 28012 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 348 KB Output is correct
2 Incorrect 202 ms 27996 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 348 KB Output is correct
2 Incorrect 203 ms 27752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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