Submission #591155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
591155	2022-07-06T23:18:16 Z	tutis	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1000 ms	13664 KB

island

/*input
4 3
4 2 2 1
1 2
3 2
4 1
*/
#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];
	vector<int>adj[N];
	while (M--)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<bool>ret(N, false);
	for (int i = 0; i < N; i++)
	{
		vector<bool>vis(N, false);
		vis[i] = true;
		ll sum = S[i];
		set<pair<int, int>>Q;
		for (int j : adj[i])
		{
			vis[j] = true;
			Q.insert({S[j], j});
		}
		int cnt = 1;
		while (!Q.empty())
		{
			int i = Q.begin()->second;
			Q.erase(Q.begin());
			if (S[i] <= sum)
			{
				sum += S[i];
				cnt++;
				for (int j : adj[i])
				{
					if (vis[j] == false)
					{
						vis[j] = true;
						Q.insert({S[j], j});
					}
				}
			}
			else
				break;
		}
		if (cnt == N)
			ret[i] = true;
	}
	for (int i : ret)
		cout << i;
	cout << "\n";
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	203 ms	428 KB	Output is correct
5	Correct	198 ms	408 KB	Output is correct
6	Correct	285 ms	428 KB	Output is correct
7	Correct	194 ms	424 KB	Output is correct
8	Correct	143 ms	408 KB	Output is correct
9	Correct	314 ms	480 KB	Output is correct
10	Correct	99 ms	440 KB	Output is correct
11	Correct	104 ms	468 KB	Output is correct
12	Correct	116 ms	448 KB	Output is correct
13	Correct	209 ms	440 KB	Output is correct
14	Correct	107 ms	340 KB	Output is correct

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	Execution timed out	1089 ms	13664 KB	Time limit exceeded
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	Execution timed out	1088 ms	12000 KB	Time limit exceeded
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	Execution timed out	1092 ms	12344 KB	Time limit exceeded
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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	203 ms	428 KB	Output is correct
5	Correct	198 ms	408 KB	Output is correct
6	Correct	285 ms	428 KB	Output is correct
7	Correct	194 ms	424 KB	Output is correct
8	Correct	143 ms	408 KB	Output is correct
9	Correct	314 ms	480 KB	Output is correct
10	Correct	99 ms	440 KB	Output is correct
11	Correct	104 ms	468 KB	Output is correct
12	Correct	116 ms	448 KB	Output is correct
13	Correct	209 ms	440 KB	Output is correct
14	Correct	107 ms	340 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Execution timed out	1089 ms	13664 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-