oj.uz

Submission #405205

# Submission time Handle Problem Language Result Execution time Memory
405205 2021-05-15T21:43:34 Z CaroLinda From Hacks to Snitches (BOI21_watchmen) C++14
5 / 100
 1045 ms 105648 KB 
#include <bits/stdc++.h>

const int MAX = 12599999 ;
const int MAXN = 1e5+10 ;

#define pb push_back
#define mk make_pair

using namespace std ;

int N , M , K ,C ;
int dist[ MAX ] ;
bool nao_pode[MAX] ;
int fila[MAX] ;
vector<int> adj[MAXN] ;

int code(int x, int y) { return (x-1)+y*100000 ; }

void bfs()
{
	int ini = 0 , fim =1 ;
	fila[0] = code(1,0) ;

	for(int i = 0 ; i < MAX ; i++ ) dist[i] = -1 ;

	dist[ code(1,0) ] = 0;

	while(ini < fim)
	{
		int x = fila[ini++] ;

		int vert = (x%100000)+1 ;
		int t = x/100000 ;


		int _x = code(vert, (t+1)%C) ;

		if( !nao_pode[_x] && dist[_x] == -1 )
		{
			dist[_x] = dist[x]+1 ;
			fila[fim++] = _x ;
		}

		for(auto e : adj[vert] ) 
		{
			int aux = code(e, (t+1)%C ) ;

			if( nao_pode[ code(e, t) ] && nao_pode[ code(vert, (t+1)%C) ] ) continue ;
			if( nao_pode[aux] ) continue ;
			if( dist[aux] != -1 ) continue ;

			dist[aux] = dist[x]+1 ;
			fila[fim++] = aux ;
 
		}

	}

}

int main()
{
	scanf("%d %d", &N, &M  ) ;

	for(int i = 1 , u , v ; i<= M ; i++ )
	{
		scanf("%d %d", &u, &v ) ;
		adj[u].pb(v) ;
		adj[v].pb(u ) ;
	}

	scanf("%d", &K ) ;
	scanf("%d", &C ) ;

	for(int i = 0 , x ; i < C ; i++ )
	{
		scanf("%d", &x ) ;
		nao_pode[ code(x,i) ] = true ;
	}

	bfs() ;

	int ans = -1 ;

	for(int i = 0 ; i < C ; i++ )
	{
		int p = code(N,i) ;
		if(dist[p] == -1) continue ;
		if(ans == -1 || dist[p] < ans ) ans = dist[p] ;
	}

	if( ans == -1 ) { printf("impossible\n") ; return 0 ; }


	printf("%d\n" , ans ) ;
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d %d", &N, &M  ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
watchmen.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d", &K ) ;
      |  ~~~~~^~~~~~~~~~~
watchmen.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d", &C ) ;
      |  ~~~~~^~~~~~~~~~~
watchmen.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d", &x ) ;
      |   ~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53532 KB Output is correct
2 Correct 1036 ms 105648 KB Output is correct
3 Correct 906 ms 100448 KB Output is correct
4 Correct 1045 ms 100500 KB Output is correct
5 Correct 24 ms 52428 KB Output is correct
6 Correct 972 ms 100392 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53580 KB Output is correct
2 Correct 1014 ms 105608 KB Output is correct
3 Correct 902 ms 100448 KB Output is correct
4 Correct 1016 ms 100504 KB Output is correct
5 Correct 24 ms 52524 KB Output is correct
6 Correct 904 ms 100596 KB Output is correct
7 Incorrect 463 ms 77604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53580 KB Output is correct
2 Correct 1014 ms 105608 KB Output is correct
3 Correct 902 ms 100448 KB Output is correct
4 Correct 1016 ms 100504 KB Output is correct
5 Correct 24 ms 52524 KB Output is correct
6 Correct 904 ms 100596 KB Output is correct
7 Incorrect 463 ms 77604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53580 KB Output is correct
2 Correct 1014 ms 105608 KB Output is correct
3 Correct 902 ms 100448 KB Output is correct
4 Correct 1016 ms 100504 KB Output is correct
5 Correct 24 ms 52524 KB Output is correct
6 Correct 904 ms 100596 KB Output is correct
7 Incorrect 463 ms 77604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53532 KB Output is correct
2 Correct 1036 ms 105648 KB Output is correct
3 Correct 906 ms 100448 KB Output is correct
4 Correct 1045 ms 100500 KB Output is correct
5 Correct 24 ms 52428 KB Output is correct
6 Correct 972 ms 100392 KB Output is correct
7 Correct 86 ms 53580 KB Output is correct
8 Correct 1014 ms 105608 KB Output is correct
9 Correct 902 ms 100448 KB Output is correct
10 Correct 1016 ms 100504 KB Output is correct
11 Correct 24 ms 52524 KB Output is correct
12 Correct 904 ms 100596 KB Output is correct
13 Incorrect 463 ms 77604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53532 KB Output is correct
2 Correct 1036 ms 105648 KB Output is correct
3 Correct 906 ms 100448 KB Output is correct
4 Correct 1045 ms 100500 KB Output is correct
5 Correct 24 ms 52428 KB Output is correct
6 Correct 972 ms 100392 KB Output is correct
7 Correct 86 ms 53580 KB Output is correct
8 Correct 1014 ms 105608 KB Output is correct
9 Correct 902 ms 100448 KB Output is correct
10 Correct 1016 ms 100504 KB Output is correct
11 Correct 24 ms 52524 KB Output is correct
12 Correct 904 ms 100596 KB Output is correct
13 Incorrect 463 ms 77604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 53532 KB Output is correct
2 Correct 1036 ms 105648 KB Output is correct
3 Correct 906 ms 100448 KB Output is correct
4 Correct 1045 ms 100500 KB Output is correct
5 Correct 24 ms 52428 KB Output is correct
6 Correct 972 ms 100392 KB Output is correct
7 Correct 86 ms 53580 KB Output is correct
8 Correct 1014 ms 105608 KB Output is correct
9 Correct 902 ms 100448 KB Output is correct
10 Correct 1016 ms 100504 KB Output is correct
11 Correct 24 ms 52524 KB Output is correct
12 Correct 904 ms 100596 KB Output is correct
13 Incorrect 463 ms 77604 KB Output isn't correct
14 Halted 0 ms 0 KB -