답안 #570319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-