제출 #1244864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244864		DeathIsAwe	경찰관과 강도 (BOI14_coprobber)	C++20	30 / 100	130 ms	3860 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, 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++) {
            wingrid[i][j] = -1;
            if (i == j) {
                wingrid[i][j] = 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++) {
            if (i == j) continue;
            nextcount[i][j] = neigh[j].size();
            if (a[i][j]) {
                nextcount[i][j] -= 1;
            }
        }
    }
    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] == -1) {
                flag = false;
            }
        }
        if (flag) {
            curpos = i;
            return i;
        }
    }
    return -1;
}

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

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