Submission #405198

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

watchmen

#include <bits/stdc++.h>

const int MAXT = 130 ;
const int MAXN = 1e5+10 ;

#define pb push_back
#define mk make_pair

using namespace std ;

int N , M , K ,C ;
int code[MAXN][MAXT] ;
int dist[ MAXN*MAXT ] ;
vector<pair<int,int> > edge ;
vector<int> adj[ MAXN*MAXT ] ;
bool nao_pode[MAXN*MAXT] ;

void bfs()
{
	int ini = 0 ;
	vector<int> fila = { code[1][0] } ;

	for(int i = 0 ; i <= code[N][C-1] ; i++ ) dist[i] = -1 ;

	dist[ code[1][0] ] = 0;

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

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

			dist[e] = dist[x]+1 ;
			fila.pb(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 ) ;

	assert( K <= 1 ) ;

	scanf("%d", &C ) ;

	for(int i = 1 , c = 0 ; i <= N ; i++ )
		for(int j = 0 ; j < C ; j++ , c++ ) code[i][j] = 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++ )
		if( dist[ code[N][i] ] != -1 && (ans == -1 || dist[code[N][i]] < ans)  && !nao_pode[code[N][i]])
			ans = dist[code[N][i]] ;

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


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

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d %d", &N, &M  ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
watchmen.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d", &K ) ;
      |  ~~~~~^~~~~~~~~~~
watchmen.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &C ) ;
      |  ~~~~~^~~~~~~~~~~
watchmen.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   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