oj.uz

답안 #613375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613375 2022-07-30T04:48:28 Z talant117408 경찰관과 강도 (BOI14_coprobber) C++17
0 / 100
 1 ms 384 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;
//~ 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);
    }
    
    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) {
            mn = dist[R][to];
            ind = to;
        }
    }
    cop = ind;
    return cop;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -