oj.uz

Submission #424999

# Submission time Handle Problem Language Result Execution time Memory
424999 2021-06-12T12:19:10 Z patrikpavic2 From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 319 ms 146068 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 129896 KB Output is correct
2 Incorrect 300 ms 146068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 129896 KB Output is correct
2 Incorrect 319 ms 145972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 129896 KB Output is correct
2 Incorrect 319 ms 145972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 129896 KB Output is correct
2 Incorrect 319 ms 145972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 129896 KB Output is correct
2 Incorrect 300 ms 146068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 129896 KB Output is correct
2 Incorrect 300 ms 146068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 129896 KB Output is correct
2 Incorrect 300 ms 146068 KB Output isn't correct
3 Halted 0 ms 0 KB -