Submission #250148

#	Time	Username	Problem	Language	Result	Execution time	Memory
250148		Kevin_Zhang_TW	경찰관과 강도 (BOI14_coprobber)	C++17	16 / 100	453 ms	3096 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
#define MAX_N 500
const int inf = 1e9;

// modify the following functions
// you can define global variables and functions
int dp[MAX_N][MAX_N];
int now, n;
vector<int> edge[MAX_N];
bool con[MAX_N][MAX_N];
bool dfs(int tar, int now, int lst) {
	if (now == tar) return true;
	for (int u : edge[now]) if (u != lst && dfs(tar, u, now))
		return true;
	return false;
}
int start(int n, bool A[MAX_N][MAX_N]) {
	int m = 0;
	for (int i = 0;i < n;++i) {
		for (int j = 0;j < n;++j) {
			con[i][j] = A[i][j];
			if (A[i][j])
				edge[i].pb(j), dp[i][j] = 1, ++m;
			else
				dp[i][j] = inf;
		}
		dp[i][i] = 0;
	}

	
	assert(m == (n-1) * 2);
//	for (int i = 0;i < n;++i)
//		for (int j = 0;j < n;++j) if (i != j)
//			assert(A[i][j]);
	for (int a:{1,1,1})
	for (int k = 0;k < n;++k)
		for (int i = 0;i < n;++i)
			for (int j = 0;j < n;++j)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

	return now = 0;
//	int res = 0;
//	for (int i = 0;i < n;++i)
//		if (dp[i][i] <= n)
//			res = max(res, dp[i][i]), cerr << dp[i][i] << '\n';
//	if (res > 4) return -1;
//
//	return 0;

}

 
int nextMove(int R) {
	if (now == R) 
		return R;
	//assert(now >= 0 and now < n);
	//assert(dp[now][R] <= n);
//	for (int i = 0;i < n;++i)
//		if (con[i][now] && dp[i][R] == dp[now][R]-1)
//			return now = i;
//	return -1;
//	for (int i= 0 ;i < n;++i)
//		if (con[now][i]) {
//			dis = min(dis, dp[i][R]);
//			if (dis == dp[i][R])
//				go = i;
//		}
//	return now = go;
	for (int u : edge[now])
		if (dfs(R, u, now)) {
			//assert(dp[u][R] == dp[now][R]-1);
			return now = u;
		}
	return -1;
} 

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:39:11: warning: unused variable 'a' [-Wunused-variable]
  for (int a:{1,1,1})
           ^

• Subtask 1: 16 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40