oj.uz

답안 #613407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613407 2022-07-30T04:54:28 Z talant117408 경찰관과 강도 (BOI14_coprobber) C++17
30 / 100
 81 ms 2744 KB 
#include "coprobber.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

const int MAXN = 503;
int n;
vector <int> graph[MAXN];
int dist[MAXN][MAXN];
int color[MAXN];
int flag = 0;
int cop = 0, last = 0;
//~ int grundy[MAXN][MAXN][2]; // cop, robber, whose move

void bfs(int v) {
    for (int i = 0; i < n; i++) dist[v][i] = 2e9;
    dist[v][v] = 0;
    queue <int> K;
    K.push(v);
    while (sz(K)) {
        auto u = K.front(); K.pop();
        for (auto to : graph[u]) {
            if (dist[v][to] > dist[v][u] + 1) {
                dist[v][to] = dist[v][u] + 1;
                K.push(to);
            } 
        }
    }
}

void dfs(int v = 0, int c = 1) {
    color[v] = c;
    for (auto to : graph[v]) {
        if (color[to]) {
            if (color[to] == color[v]) {
                flag = -1;
            }
        }
        else {
            dfs(to, 3 - c);
        }
    }
}

int start(int N, bool A[MAX_N][MAX_N]) {
    n = N;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j]) {
                graph[i].pb(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bfs(i);
    }
    dfs();
    
    return flag;
}

int nextMove(int R) {
    if (color[cop] == color[R]) return cop;
    
    int mn = 2e9, ind = -1;
    for (auto to : graph[cop]) {
        if (dist[R][to] < mn && last != to) {
            mn = dist[R][to];
            ind = to;
        }
    }
    last = cop;
    cop = ind;
    return cop;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 51 ms 2688 KB Output is correct
5 Correct 18 ms 1300 KB Output is correct
6 Correct 59 ms 2576 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 46 ms 2744 KB Output is correct
4 Correct 44 ms 2728 KB Output is correct
5 Correct 52 ms 2692 KB Output is correct
6 Correct 81 ms 2588 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 0 ms 336 KB Cop can catch the robber, but start() returned -1
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 51 ms 2688 KB Output is correct
5 Correct 18 ms 1300 KB Output is correct
6 Correct 59 ms 2576 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 46 ms 2744 KB Output is correct
10 Correct 44 ms 2728 KB Output is correct
11 Correct 52 ms 2692 KB Output is correct
12 Correct 81 ms 2588 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Incorrect 0 ms 336 KB Cop can catch the robber, but start() returned -1
19 Halted 0 ms 0 KB -