Submission #570319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
570319	2022-05-29T08:20:59 Z	장태환(#8350)	From Hacks to Snitches (BOI21_watchmen)	C++17	5 / 100	2007 ms	56156 KB

watchmen

#include <bits/stdc++.h>
//If you have fancy wingsuit t you won in your national computer science competition, then you can make a living from prizes awarded at computer science competitions
using namespace std;
vector<int>link[100100];
int mint[100100][125];
int arr[125];
int main()
{
	int N, K;
	cin >> N >> K;
	int i;
	for (i = 0; i < K; i++)
	{
		int a, b;
		cin >> a >> b;
		link[a].push_back(b);
		link[b].push_back(a);
	}
	for (i = 1; i <= N; i++)
		link[i].push_back(i);
	queue<pair<int, int>>t;
	int garvz,M;
	cin >> garvz>>M;
	for (i = 0; i < M; i++)
	{
		cin >> arr[i];
	}
	arr[M] = arr[i];
	t.push({ 1,0 });
	memset(mint, -1, sizeof(mint));
	mint[1][0] = 0;
	while (t.size())
	{
		auto r = t.front();
		t.pop();
		if (r.first == N)
		{
			cout << mint[r.first][r.second];
			return 0;
		}
		int j;
		for (j = 0; j < link[r.first].size(); j++)
		{
			int n = link[r.first][j];
			if (r.first == arr[r.second] || n == arr[r.second + 1] || r.first == arr[r.second + 1] && n == arr[r.second])
				continue;
			if (mint[n][(r.second + 1) % M]>=0)
				continue;
			mint[n][(r.second + 1) % M] = mint[r.first][r.second] + 1;
			t.push({ n,(r.second + 1) % M });
		}
	}
	cout << "impossible";
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (j = 0; j < link[r.first].size(); j++)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:45:91: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |    if (r.first == arr[r.second] || n == arr[r.second + 1] || r.first == arr[r.second + 1] && n == arr[r.second])
      |                                                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	53064 KB	Output is correct
2	Correct	629 ms	55792 KB	Output is correct
3	Correct	1006 ms	56004 KB	Output is correct
4	Correct	2007 ms	56136 KB	Output is correct
5	Correct	29 ms	51552 KB	Output is correct
6	Correct	1283 ms	56040 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	53032 KB	Output is correct
2	Correct	692 ms	55888 KB	Output is correct
3	Correct	1043 ms	55896 KB	Output is correct
4	Correct	1591 ms	56156 KB	Output is correct
5	Correct	27 ms	51556 KB	Output is correct
6	Correct	1321 ms	56032 KB	Output is correct
7	Incorrect	490 ms	55904 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	53032 KB	Output is correct
2	Correct	692 ms	55888 KB	Output is correct
3	Correct	1043 ms	55896 KB	Output is correct
4	Correct	1591 ms	56156 KB	Output is correct
5	Correct	27 ms	51556 KB	Output is correct
6	Correct	1321 ms	56032 KB	Output is correct
7	Incorrect	490 ms	55904 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	53032 KB	Output is correct
2	Correct	692 ms	55888 KB	Output is correct
3	Correct	1043 ms	55896 KB	Output is correct
4	Correct	1591 ms	56156 KB	Output is correct
5	Correct	27 ms	51556 KB	Output is correct
6	Correct	1321 ms	56032 KB	Output is correct
7	Incorrect	490 ms	55904 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	53064 KB	Output is correct
2	Correct	629 ms	55792 KB	Output is correct
3	Correct	1006 ms	56004 KB	Output is correct
4	Correct	2007 ms	56136 KB	Output is correct
5	Correct	29 ms	51552 KB	Output is correct
6	Correct	1283 ms	56040 KB	Output is correct
7	Correct	62 ms	53032 KB	Output is correct
8	Correct	692 ms	55888 KB	Output is correct
9	Correct	1043 ms	55896 KB	Output is correct
10	Correct	1591 ms	56156 KB	Output is correct
11	Correct	27 ms	51556 KB	Output is correct
12	Correct	1321 ms	56032 KB	Output is correct
13	Incorrect	490 ms	55904 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	53064 KB	Output is correct
2	Correct	629 ms	55792 KB	Output is correct
3	Correct	1006 ms	56004 KB	Output is correct
4	Correct	2007 ms	56136 KB	Output is correct
5	Correct	29 ms	51552 KB	Output is correct
6	Correct	1283 ms	56040 KB	Output is correct
7	Correct	62 ms	53032 KB	Output is correct
8	Correct	692 ms	55888 KB	Output is correct
9	Correct	1043 ms	55896 KB	Output is correct
10	Correct	1591 ms	56156 KB	Output is correct
11	Correct	27 ms	51556 KB	Output is correct
12	Correct	1321 ms	56032 KB	Output is correct
13	Incorrect	490 ms	55904 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	53064 KB	Output is correct
2	Correct	629 ms	55792 KB	Output is correct
3	Correct	1006 ms	56004 KB	Output is correct
4	Correct	2007 ms	56136 KB	Output is correct
5	Correct	29 ms	51552 KB	Output is correct
6	Correct	1283 ms	56040 KB	Output is correct
7	Correct	62 ms	53032 KB	Output is correct
8	Correct	692 ms	55888 KB	Output is correct
9	Correct	1043 ms	55896 KB	Output is correct
10	Correct	1591 ms	56156 KB	Output is correct
11	Correct	27 ms	51556 KB	Output is correct
12	Correct	1321 ms	56032 KB	Output is correct
13	Incorrect	490 ms	55904 KB	Output isn't correct
14	Halted	0 ms	0 KB	-