oj.uz

Submission #477133

# Submission time Handle Problem Language Result Execution time Memory
477133 2021-09-30T18:57:47 Z Lobo Cop and Robber (BOI14_coprobber) C++17
0 / 100
 1 ms 328 KB 
#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define MAX_N 500

#define maxn 510

// modify the following functions
// you can define global variables and functions

ii n, mark[maxn][maxn][2], dp[maxn][maxn][2], act;
vector<ii> g[maxn];

ii sol(ii u1, ii u2, ii p) {
    if(mark[u1][u2][p] == 2) return dp[u1][u2][p];
    if(mark[u1][u2][p] == 1) return 0;
    
    mark[u1][u2][p] = 1;

    ii ans = 0;
    if(u1 == u2) {
        mark[u1][u2][p] = 2;
        return dp[u1][u2][p] = 1;
    }

    if(p == 0) {
        ans = sol(u1,u2,1);

        for(auto v : g[u1]) {
            ans = max(ans, sol(v,u2,1));
        }
    }
    else {
        for(auto v : g[u2]) {
            ans = min(ans, sol(u1,v,0));
        }
    }

    mark[u1][u2][p] = 2;

    return dp[u1][u2][p] = ans;
}


int start(int N, bool A[MAX_N][MAX_N]) {
    for(ii i = 0; i < N; i++) {
        for(ii j = 0; j < N; j++) {
            if(A[i][j]) g[i].pb(j);
        }
    }

    for(ii i = 0; i < N; i++)
        for(ii j = 0; j < N; j++)
            //cout << i << " " << j << " = " << sol(i,j,0) << endl;

    for(ii i = 0; i < N; i++) {
        bool ok = true;
        for(ii j = 0; j < N; j++) {
            if(sol(i,j,0) == 0) ok = false;
        }

        if(ok) {
            act = i;
            return i;
        }
    }

    return -1;

}

int nextMove(int R) {
    for(auto v : g[act]) {
        if(sol(v,R,1) == 1) {
            act = v;
            return v;
        }
    }
    return 0;
}

Subtask #1
0 / 16.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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