oj.uz

Submission #570330

# Submission time Handle Problem Language Result Execution time Memory
570330 2022-05-29T08:43:41 Z 장태환(#8350) From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 6000 ms 12072 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];
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 == rc.first)
			rc.second++;
		else
			rc.second = 0;
		rc.first = r.first;
		if (rc.second >= 400)
			break;
		if (r.first == N)
		{
			cout << mint[r.first];
			return 0;
		}
		int j;
		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;
			}
			
			
			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:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (j = 0; j < link[r.first].size(); j++)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~
watchmen.cpp:66:141: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |     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:74:8: warning: unused variable 'd' [-Wunused-variable]
   74 |    int d;
      |        ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9416 KB Output is correct
2 Execution timed out 6017 ms 12072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9364 KB Output is correct
2 Execution timed out 6047 ms 11868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9364 KB Output is correct
2 Execution timed out 6047 ms 11868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9364 KB Output is correct
2 Execution timed out 6047 ms 11868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9416 KB Output is correct
2 Execution timed out 6017 ms 12072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9416 KB Output is correct
2 Execution timed out 6017 ms 12072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9416 KB Output is correct
2 Execution timed out 6017 ms 12072 KB Time limit exceeded
3 Halted 0 ms 0 KB -