Submission #1244806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244806		DeathIsAwe	Cop and Robber (BOI14_coprobber)	C++20	0 / 100	0 ms	328 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int wingrid[MAX_N][MAX_N], n, a[MAX_N][MAX_N], nextcount[MAX_N][MAX_N];
int curpos;


int start(int N, bool A[MAX_N][MAX_N]) {
    n = N;
    vector<vector<int>> neigh(n);
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            a[i][j] = A[i][j];
            wingrid[i][j] = -1;
            if (i == j) {
                wingrid[i][j] = 1;
            }
            for (int k=0;k<n;k++) {
                if (a[j][k] && j != k && j != i && k != i) {
                    nextcount[i][j] += 1; 
                    nextcount[i][k] += 1;
                }
            }
            if (a[i][j]) {
                neigh[i].pb(j);
                neigh[j].pb(i);
            }
        }
    }
    //for (int i=0;i<n;i++) {
    //    for (int j=0;j<n;j++) {
    //        cout << nextcount[i][j] << ' ';
    //    }
    //    cout << endl;
    //}
    deque<pair<int,int>> check;
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (a[i][j]) {
                wingrid[i][j] = j;
                wingrid[j][i] = i;
                for (int k: neigh[j]) {
                    if (k != i) {
                        nextcount[i][k] -= 1;
                        if (nextcount[i][k] == 0) check.pb(mp(i, k));
                    }
                }
                for (int k: neigh[i]) {
                    if (k != j) {
                        nextcount[j][k] -= 1;
                        if (nextcount[j][k] == 0) check.pb(mp(j, k));
                    }
                }
            }
        }
    }
    while (check.size() > 1) {
        int siz = check.size();
        for (int i=0;i<siz;i++) {
            pair<int,int> curpair = check[0]; check.pop_front();
            for (int j=0;j<n;j++) {
                if ((a[j][curpair.ff] && j != curpair.ss) || j == curpair.ff) {
                    if (wingrid[j][curpair.ss] == -1) {
                        wingrid[j][curpair.ss] = curpair.ff;
                        for (int k: neigh[curpair.ss]) {
                            if (k != j) {
                                nextcount[j][k] -= 1;
                                if (nextcount[j][k] == 0) check.pb(mp(j, k));
                            }
                        }
                    }
                }
            }
        }
    }
    bool flag = false;
    for (int i=0;i<n;i++) {
        flag = true;
        for (int j=0;j<n;j++) {
            if (wingrid[i][j] == 0) {
                flag = false;
            }
        }
        if (flag) {
            curpos = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    return wingrid[curpos][R];
}

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