oj.uz

Submission #103455

# Submission time Handle Problem Language Result Execution time Memory
103455 2019-03-30T18:28:57 Z wilwxk Cop and Robber (BOI14_coprobber) C++11
30 / 100
 48 ms 4832 KB 
#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN=505;
int gg[MAXN][MAXN];
vector<int> g[MAXN];
int dist[MAXN][MAXN];
int marc[MAXN][MAXN];
int n, cur;

void bfs(int ori) {
	queue<int> qu; qu.push(ori);
	dist[ori][ori]=0;

	while(qu.size()) {
		int cur=qu.front(); qu.pop();
		for(auto viz : g[cur]) {
			if(dist[ori][viz]!=-1) continue;
			qu.push(viz);
			dist[ori][viz]=dist[ori][cur]+1;
		}
	}
}

int start(int N, bool V[MAX_N][MAX_N])
{
	n=N;
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			gg[i][j]=V[i][j];
			if(gg[i][j]) g[i].push_back(j);
		}
	}
	memset(dist, -1, sizeof(dist));
	for(int i=0; i<n; i++) bfs(i);

	//for(int i=0; i<n; i++) for(int j=i; j<n; j++) printf("dist %d %d > %d\n", i, j, dist[i][j]);

	cur=0;
    return 0;
}

int nextMove(int R)
{
	int melhor=cur; int menor=n;
	for(auto viz : g[cur]) {
		if(marc[viz][R]) continue;
		if(dist[viz][R]<=menor) melhor=viz, menor=dist[viz][R];
	}
	cur=melhor;
	marc[cur][R]=1;
    return cur;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 47 ms 4832 KB Output is correct
5 Correct 13 ms 2560 KB Output is correct
6 Correct 48 ms 3708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 46 ms 3832 KB Output is correct
4 Correct 47 ms 4216 KB Output is correct
5 Correct 43 ms 3836 KB Output is correct
6 Correct 46 ms 4556 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 3 ms 1408 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1408 KB Output is correct
6 Correct 2 ms 1408 KB Output is correct
7 Incorrect 3 ms 1408 KB Cop cannot catch the robber, but start() did not return -1
8 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 2 ms 1408 KB Output is correct
4 Correct 46 ms 4772 KB Output is correct
5 Correct 13 ms 2560 KB Output is correct
6 Correct 47 ms 3704 KB Output is correct
7 Correct 3 ms 1408 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 47 ms 3900 KB Output is correct
10 Correct 48 ms 4120 KB Output is correct
11 Correct 43 ms 3832 KB Output is correct
12 Correct 46 ms 4600 KB Output is correct
13 Correct 2 ms 1408 KB Output is correct
14 Incorrect 3 ms 1408 KB Cop cannot catch the robber, but start() did not return -1
15 Halted 0 ms 0 KB -