Submission #424999

#	Time	Username	Problem	Language	Result	Execution time	Memory
424999		patrikpavic2	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	319 ms	146068 KiB

watchmen

#include <cstdio>
#include <vector>
#include <cstring>

#define PB push_back
#define X first
#define Y second

using namespace std;

const int N = 3e5 + 500;
const int K = 15;

int rit[N], kad[N], dis[N], tko[N];
vector < int > doso[K * N], v[N];
int n, m;

bool dobar(int cv, int ds){
	if(!rit[cv]) return true;
	return ds % rit[cv] != kad[cv];
}

int main(){
	memset(dis, -1, sizeof(dis));
	scanf("%d%d", &n, &m);
	for(int i = 0;i < m;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	int q; scanf("%d", &q);
	for(;q--;){
		int ln; scanf("%d", &ln);
		for(int i = 0;i < ln;i++){
			int x; scanf("%d", &x);
			rit[x] = ln, kad[x] = i; tko[x] = q + 1;
		}
	}
	doso[0].PB(1);
	for(int i = 0;i < K * N;i++){
		for(int x : doso[i]){
			if(dis[x] != -1) continue;
			dis[x] = i; 
			for(int k = 0;k < K;k++){
				if(!dobar(x, dis[x] + k)) break;
				for(int y : v[x]){
					if((tko[x] != tko[y] || !tko[x]) && dobar(y, dis[x] + k + 1))
						doso[dis[x] + k + 1].PB(y);
					if(tko[x] == tko[y] && dobar(y, dis[x] + k + 1) 
						&& !(kad[x] == (kad[y] + 1) % rit[x] && !dobar(y, dis[x] + k)))
						doso[dis[x] + k + 1].PB(y);
				}
			}
		}
	}
	if(dis[n] == -1)
		printf("impossible\n");
	else
		printf("%d\n", dis[n]);
	return 0;
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
watchmen.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
watchmen.cpp:32:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   int ln; scanf("%d", &ln);
      |           ~~~~~^~~~~~~~~~~
watchmen.cpp:34:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20