oj.uz

Submission #570333

# Submission time Handle Problem Language Result Execution time Memory
570333 2022-05-29T08:46:48 Z 장태환(#8350) From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1379 ms 12104 KB 
#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[300100];
int mint[300100];
int ce[300100];
vector<vector<int>>arr;
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 g,M;
	cin >> g;
	for (i = 0; i < g; i++)
	{
		vector<int>Tr;
		cin >> M;
		while (M--)
		{
			int a;
			cin >> a;
			Tr.push_back(a);
		}
		arr.push_back(Tr);
	}
	t.push({ 1,0 });
	memset(mint, -1, sizeof(mint));
	mint[1] = 0;
	pair<int, int>rc = { 0,0 };
	while (t.size())
	{
		auto r = t.front();
		t.pop();
		if (r.first == N)
		{
			cout << mint[N];
			return 0;
		}
		int j;
		int ccd = 0;
		for (j = 0; j < link[r.first].size(); j++)
		{
			
			int n = link[r.first][j];
			if (n!=r.first&&mint[n] >= 0)
				continue;
			int k;
			for (k = 0; k < g; k++)
			{
				if (r.first == arr[k][r.second % arr[k].size()] || n == arr[k][(r.second + 1) % arr[k].size()] || n == arr[k][r.second % arr[k].size()] && r.first == arr[k][(r.second + 1) % arr[k].size()] )
					goto T;
			}
			if (j + 1 != link[r.first].size())
				ccd++;
			else
			{
				if (ccd)
					ce[r.first] = 0;
				else
					ce[r.first]++;
				if (ce[r.first] >= 400)
					break;
			}
			mint[n] = mint[r.first] + 1;
			t.push({ n,(r.second + 1)});
			T:
			int d;

		}
		
	}
	cout << "impossible";
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (j = 0; j < link[r.first].size(); j++)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:61:141: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |     if (r.first == arr[k][r.second % arr[k].size()] || n == arr[k][(r.second + 1) % arr[k].size()] || n == arr[k][r.second % arr[k].size()] && r.first == arr[k][(r.second + 1) % arr[k].size()] )
watchmen.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    if (j + 1 != link[r.first].size())
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:78:8: warning: unused variable 'd' [-Wunused-variable]
   78 |    int d;
      |        ^
watchmen.cpp:40:16: warning: variable 'rc' set but not used [-Wunused-but-set-variable]
   40 |  pair<int, int>rc = { 0,0 };
      |                ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9424 KB Output is correct
2 Incorrect 1291 ms 12036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9464 KB Output is correct
2 Incorrect 1379 ms 12104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9464 KB Output is correct
2 Incorrect 1379 ms 12104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9464 KB Output is correct
2 Incorrect 1379 ms 12104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9424 KB Output is correct
2 Incorrect 1291 ms 12036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9424 KB Output is correct
2 Incorrect 1291 ms 12036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9424 KB Output is correct
2 Incorrect 1291 ms 12036 KB Output isn't correct
3 Halted 0 ms 0 KB -