Submission #309740

#	Time	Username	Problem	Language	Result	Execution time	Memory
309740		nicolaalexandra	Cop and Robber (BOI14_coprobber)	C++14	60 / 100	3088 ms	11420 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
//#define MAX_N 510
using namespace std;

int C,R;
struct stare{
    int c,r,t;
};
stare d[MAX_N*MAX_N*3];
int dp[MAX_N][MAX_N][2],fth[MAX_N][MAX_N];
vector <int> L[MAX_N];

int start (int n, bool a[MAX_N][MAX_N]){
    /// stari de pierdere / de castig
    /// C,R,0/1 - unde se afla politistu si hotu si cine a facut ultima miscare
    /// C,C,0/1 - stare de castig

    int p = 1, u = 0;
    for (int i=0;i<n;++i){
        dp[i][i][0] = dp[i][i][1] = 1;
        d[++u] = {i,i,0};
        d[++u] = {i,i,1};
        L[i].push_back(i);
    }

    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
            if (a[i][j]){
                L[i].push_back(j);
                L[j].push_back(i);
            }

    while (p <= u){
        int c = d[p].c, r = d[p].r, t = d[p].t; /// stare castigatoare
        ++p;

        if (!t){ /// trb sa mute hotu
            for (auto i : L[r]){
                if (i == r || !a[r][i] || dp[c][i][1])
                    continue;

                /// daca toti vecinii lui i au stare de castig atunci si asta e stare de castig
                int ok = 1;
                for (auto vecin : L[i])
                    if (a[i][vecin] && !dp[c][vecin][0]){
                        ok = 0;
                        break;
                    }

                if (ok){
                    dp[c][i][1] = 1;
                    d[++u] = {c,i,1};
                }}

        } else { /// politistul se muta sau sta pe loc
            for (auto i : L[c]){
                if ((!a[c][i] && i != c) || dp[i][r][0])
                    continue;

                dp[i][r][0] = 1;
                fth[i][r] = c; /// unde ma duc din starea asta
                d[++u] = {i,r,0};
                }}}

    for (int i=0;i<n;i++){
        int ok = 1;
        for (int j=0;j<n;j++)
            if (!dp[i][j][0]){
                ok = 0;
                break;
            }
        if (ok)
            return i;
    }
    return -1;

}

int nextMove (int R){

    C = fth[C][R];
    return C;
}

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40