oj.uz

Submission #957787

# Submission time Handle Problem Language Result Execution time Memory
957787 2024-04-04T10:25:56 Z hariaakas646 Cop and Robber (BOI14_coprobber) C++17
0 / 100
 57 ms 24224 KB 
#include "coprobber.h"
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

vvi graph;
int n;
bool vis[510][510][2];
bool win[510][510][2];
int nex[510][510][2];

bool dfs(int c, int r, int t) {
    if(vis[c][r][t]) return win[c][r][t];
    vis[c][r][t] = true;
    if(c == r) {
        win[c][r][t] = true;
        nex[c][r][t] = c;
        return true;
    }
    if(t == 1) {
        bool w = dfs(c, r, !t);
        int nx=-1;
        if(w) nx = c;
        for(auto e : graph[c]) {
            bool out = dfs(e, r, !t);
            if(out) {
                w = true;
                nx = e;
            }
        }
        win[c][r][t] = w;
        nex[c][r][t] = nx;
    }
    else {
        bool w = true;
        for(auto e : graph[r]) {
            bool out = dfs(c, e, !t);
            if(!out) {
                w = false;
            }
        }
        win[c][r][t] = w;
    }
    return win[c][r][t];
}

int pos = -1;

int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;
    graph = vvi(n);

    frange(i, n) {
        frange(j, n) {
            if(A[i][j]) graph[i].pb(j);
            win[i][j][0] = win[i][j][1] = false;
            vis[i][j][0] = vis[i][j][1] = false;
            nex[i][j][0] = nex[i][j][1] = -1;
        }
    }

    frange(i, n) {
        frange(j, n) {
            dfs(i, j, 1);
            dfs(i, j, 0);
        }
    }
    bool w = false;
    int nx = -1;
    frange(i, n) {
        bool curr = true;
        frange(j, n) {
            if(!win[i][j][1]) curr = false;
        }
        if(curr) {
            w = true;
            nx = i;
        }
    }
    pos = nx;
    return nx;
}

int nextMove(int R)
{
    return nex[pos][R][1];
}

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:91:10: warning: variable 'w' set but not used [-Wunused-but-set-variable]
   91 |     bool w = false;
      |          ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Incorrect 57 ms 24224 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Incorrect 57 ms 24224 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -