oj.uz

Submission #677488

# Submission time Handle Problem Language Result Execution time Memory
677488 2023-01-03T13:02:08 Z dooompy Cop and Robber (BOI14_coprobber) C++17
0 / 100
 1 ms 464 KB 
#include "bits/stdc++.h"
#include "coprobber.h"
 
 
using namespace std;
 
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
 
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
 
using ll = long long;
 
struct state {
    int cop, robber, move;
};
 
vector<int> adj[505];
int dp[505][505][2];
int moves[505][505][2]; // 0 - cops turn, 1 - robbers turn
int ct[505][505];
 
int pos = 0;
 
int start(int n, bool a[500][500]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) {
                adj[i].push_back(j);
            }
        }
    }
 
    queue<state> states;
 
    for (int i = 0; i < n; i++) {
        states.push({i, i, 0});
        states.push({i, i, 1});
 
        dp[i][i][0] = dp[i][i][1] = true;
        moves[i][i][0] = moves[i][i][1] = i;
    }
 
    while (!states.empty()) {
        auto [cop, robber, move] = states.front(); states.pop();
 
        if (move == 0) {
            // robber just moved to this square
 
            for (auto nxt : adj[robber]) {
                ct[cop][nxt]++;
 
                if (ct[cop][nxt] == adj[nxt].size()) {
                    // forced to move
                    dp[cop][nxt][1] = 1;
                    states.push({cop, nxt, 1});
                }
            }
        } else {
            for (auto nxt : adj[cop]) {
                if (dp[nxt][robber][0] == 1) continue;
                dp[nxt][robber][0] = 1;
                moves[nxt][robber][0] = cop;
                states.push({nxt, robber, 0});
            }
 
            if (dp[cop][robber][0] != 1) {
                dp[cop][robber][0] = 1;
                moves[cop][robber][0] = cop;
                states.push({cop, robber, 0});
            }
        }
    }
 
    int ok = 0;
    for (int i = 0; i < n; i++) {
        if (dp[0][i][0] != 1) {
            ok = -1;
            break;
        }
    }
 
    return ok;
}
 
int nextMove(int r) {
    return moves[pos][r][0];
}

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:73:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 if (ct[cop][nxt] == adj[nxt].size()) {
      |                     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Incorrect 1 ms 464 KB the situation repeated
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB the situation repeated
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 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 -