Submission #861199

#	Time	Username	Problem	Language	Result	Execution time	Memory
861199		Ellinor	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	58 ms	15784 KiB

coprobber

#include "coprobber.h"

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

// inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1e15;
ll mod = 1e9 + 7;

// #define int ll
#define float double

int n;
vector<vector<int>> adj;
int cat = -1;

vector<vector<vector<pii>>> dp;
queue<array<int, 3>> q;

void sol(int C, int R, int T)
{
    // if (dp[C][R][T].first != -1) return dp[C][R][T].first; // :(
    if (C == R) {
        dp[C][R][T].first = 1;
    }
    
    if (T == 1) {
        for (int i : adj[R]) {
            if (dp[C][i][0].first == -1) q.push({C, i, 0});
        }
        if (dp[C][R][0].first == -1) q.push({C, R, 0});
    }

    else if (T == 0) {
        if (C != R) {
            for (int i : adj[R]) {
                if (dp[C][i][1].first != 1) {
                    dp[C][R][0].first = 0;
                    return;
                }
            }
        }
        dp[C][R][0].first = 1;
        for (int i : adj[C]) {
            if (dp[i][R][1].first == -1) {
                dp[i][R][1].first = 1;
                dp[i][R][1].second = C;
                q.push({i, R, 1});
            }
        }
    }
}


int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;
    adj.assign(n, {});
    rep(i,0,n) {
        rep(j,i + 1,n) {
            if (A[i][j]) {
                adj[i].pb(j);
                adj[j].pb(i);
            }
        }
    }

    //
    dp.assign(n, vector<vector<pii>>(n, vector<pii>(2, {-1, -1})));
    rep(i,0,n) {
        q.push({i, i, 0});
        q.push({i, i, 1});
    }

    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        sol(x[0], x[1], x[2]);
    }

    // rep(i,0,n) {
    //     rep(j,0,n) {
    //         rep(k,0,2) {
    //             cerr << dp[i][j][k].first << " ";
    //         }
    //         cerr << endl;
    //     }
    //     cerr << endl;
    // }

    rep(i,0,n) {
        bool w = true;
        rep(j,0,n) {
            if (dp[i][j][1].first != 1) w = false;
        }
        if (w) {
            return cat = i;
        }
    }

    return -1;
}

int nextMove(int R)
{
    if (cat == R) return cat; //
    return cat = dp[cat][R][1].second;
}

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