Submission #957787

#	Time	Username	Problem	Language	Result	Execution time	Memory
957787		hariaakas646	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	57 ms	24224 KiB

coprobber

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40