Submission #861510

#	Time	Username	Problem	Language	Result	Execution time	Memory
861510		Ellinor	Cop and Robber (BOI14_coprobber)	C++14	100 / 100	608 ms	20740 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;

vector<vector<int>> r_edges_left;

void sol(int C, int R, int T)
{
    // cerr << C << " " << R << " " << T << "\n";
    
    if (T == 1) {
        for (int i : adj[R]) {
            r_edges_left[C][i]--;
            // cerr << "-- " << C << " " << i << " status : " << r_edges_left[C][i] << "\n";
            if (r_edges_left[C][i] == 0 && dp[C][i][0].first == -1) {
                q.push({C, i, 0});
            }
        }
    }

    else if (T == 0) {
        if (dp[C][R][1].first == -1) {
            dp[C][R][1].first = 1;
            dp[C][R][1].second = C;
            q.push({C, R, 1});
        }
        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});
        dp[i][i][0].first = 1;
        dp[i][i][1].first = 1;
    }

    r_edges_left.assign(n, vector<int>(n, -1));
    rep(i,0,n) {
        rep(j,0,n) {
            r_edges_left[i][j] = adj[j].size();
        }
    }

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