제출 #477133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477133		Lobo	경찰관과 강도 (BOI14_coprobber)	C++17	0 / 100	1 ms	328 KiB

coprobber

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