Submission #405203

#	Time	Username	Problem	Language	Result	Execution time	Memory
405203		CaroLinda	From Hacks to Snitches (BOI21_watchmen)	C++14	0 / 100	936 ms	524292 KiB

watchmen

#include <bits/stdc++.h>

const int MAX = 12599999 ;

#define pb push_back
#define mk make_pair

using namespace std ;

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

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++] ;

		for(auto e : adj[x] ) 
		{
			if( dist[e] != -1  ) continue ;
			if( nao_pode[e] ) continue ;

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

	}

}

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

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

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

	for(int i = 1 ; i <= N ; i++ )
		for(int j = 0 ; j < C ; j++ )
			adj[ code(i,j) ].pb( code(i,(j+1)%C) ) ;

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

	for(auto &e : edge )
		for(int g = 0 ; g < 2 ; g++ , swap(get<0>(e) , get<1>(e)))
			for(int i = 0 ; i < C ; i++ )
			{
				if( nao_pode[ code(get<1>(e),i) ] && nao_pode[ code(get<0>(e),(i+1)%C) ] ) continue ;
				adj[ code(get<0>(e),i) ].pb( code(get<1>(e),(i+1)%C ) ) ;
			}

	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:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d %d", &N, &M  ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
watchmen.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d", &K ) ;
      |  ~~~~~^~~~~~~~~~~
watchmen.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d", &C ) ;
      |  ~~~~~^~~~~~~~~~~
watchmen.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   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