Submission #405205

#	Time	Username	Problem	Language	Result	Execution time	Memory
405205		CaroLinda	From Hacks to Snitches (BOI21_watchmen)	C++14	5 / 100	1045 ms	105648 KiB

watchmen

#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 (stderr)

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 / 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