Submission #1109459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109459		Kirill22	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	463 ms	15032 KiB

coprobber

#include "coprobber.h"
#include "bits/stdc++.h"

using namespace std;

// modify the following functions
// you can define global variables and functions
int n;
int dp[2][MAX_N][MAX_N], cnt[2][MAX_N][MAX_N], par[MAX_N][MAX_N];
int pos = 0;
vector<int> g[MAX_N];

int start(int N, bool A[MAX_N][MAX_N]) {
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j]) {
                g[i].push_back(j);
            }
        }
    }
    vector<array<int, 3>> tmp;
    for (int i = 0; i < n; i++) {
        dp[1][i][i] = 1;
        dp[0][i][i] = 1;
        par[i][i] = i;
        tmp.push_back({1, i, i});
        tmp.push_back({0, i, i});
    }
    for (int it = 0; it < (int) tmp.size(); it++) {
        auto [t, x, y] = tmp[it];
//        cout << t << " " << x << " " << y << " " << dp[t][x][y] << endl;
        if (t == 0) {
            auto var = g[y];
            for (auto y2 : var) {
                if (dp[t ^ 1][x][y2] != 0) {
                    continue;
                }
                cnt[t ^ 1][x][y2]++;
                if (cnt[t ^ 1][x][y2] == (int) g[y2].size()) {
                    dp[t ^ 1][x][y2] = 1;
                    tmp.push_back({(t ^ 1), x, y2});
                }
            }
        } else {
            auto var = g[x]; var.push_back(x);
            for (auto x2 : var) {
                if (dp[t ^ 1][x2][y] != 0) {
                    continue;
                }
                par[x2][y] = x;
                dp[t ^ 1][x2][y] = 1;
                tmp.push_back({(t ^ 1), x2, y});
            }
        }
    }
    for (int i = 0; i < n; i++) {
        int win = 0;
        for (int j = 0; j < n; j++) {
            if (dp[0][i][j] == 1) {
                win++;
            }
        }
        if (win == n) {
            pos = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    int mem = par[pos][R];
    pos = mem;
    return mem;
}

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