Submission #54994

#	Time	Username	Problem	Language	Result	Execution time	Memory
54994		cki86201	Cop and Robber (BOI14_coprobber)	C++11	100 / 100	446 ms	12000 KiB

coprobber

#include "coprobber.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
#include <complex.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int d[2][510][510], nxt[510][510], cnt[510][510];
int deg[510];
vector <t3> V;
int now_p;

int start(int N, bool A[MAX_N][MAX_N])
{
    rep(i, N) rep(j, N) deg[i] += A[i][j];
    rep(i, N) rep(k, 2) V.pb(t3(k, i, i)), d[k][i][i] = 1, nxt[i][i] = -1;
    rep(i,szz(V)) {
        int t, p, r;
        tie(t, p, r) = V[i];
        if(t == 0) {
            rep(j, N) if(A[r][j]) {
                if(d[1][p][j] == 0) {
                    cnt[p][j]++;
                    if(cnt[p][j] == deg[j]) {
                        d[1][p][j] = 1;
                        V.pb(t3(1, p, j));
                    }
                }
            }
        }
        else {
            rep(j, N) if(A[p][j] || j == p) {
                if(d[0][j][r] == 0) {
                    nxt[j][r] = p;
                    d[0][j][r] = 1;
                    V.pb(t3(0, j, r));
                }
            }
        }
    }
    rep(i, N) {
        int ok = 1;
        rep(j, N) if(d[0][i][j] == 0) { ok = 0; break; }
        if(ok) return now_p = i;
    }
    return -1;
}

int nextMove(int R)
{
    return now_p = nxt[now_p][R];
}

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