제출 #1075938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1075938		oscar1f	경찰관과 강도 (BOI14_coprobber)	C++17	100 / 100	235 ms	7148 KiB

coprobber

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

const int TAILLE_MAX=500+5;
int nbSom,nbAre,poliCour;
bool existeChem[TAILLE_MAX][TAILLE_MAX];
vector<int> adja[TAILLE_MAX];
int memo[TAILLE_MAX][TAILLE_MAX][2];
int suiv[TAILLE_MAX][TAILLE_MAX];
int degSort[TAILLE_MAX];
int rest[TAILLE_MAX][TAILLE_MAX];

void maj(int posPoli,int posVol,int tour) {
    if (memo[posPoli][posVol][tour]==1) {
        memo[posPoli][posVol][tour]=0;
        if (tour==1) {
            for (int i:adja[posPoli]) {
                if (memo[i][posVol][0]==1) {
                    suiv[i][posVol]=posPoli;
                    maj(i,posVol,0);
                }
            }
            if (memo[posPoli][posVol][0]==1) {
                suiv[posPoli][posVol]=posPoli;
                maj(posPoli,posVol,0);
            }
        }
        else {
            for (int i:adja[posVol]) {
                rest[posPoli][i]--;
                if (rest[posPoli][i]==0) {
                    maj(posPoli,i,1);
                }
            }
        }
    }
}

int start(int N, bool A[MAX_N][MAX_N]) {
    nbSom=N;
    for (int i=0;i<nbSom;i++) {
        for (int j=0;j<nbSom;j++) {
            existeChem[i][j]=A[i][j];
            if (existeChem[i][j]) {
                adja[i].push_back(j);
                degSort[i]++;
            }
            memo[i][j][0]=1;
            memo[i][j][1]=1;
        }
    }
    for (int i=0;i<nbSom;i++) {
        for (int j=0;j<nbSom;j++) {
            rest[i][j]=degSort[j];
        }
    }
    for (int i=0;i<nbSom;i++) {
        maj(i,i,0);
        maj(i,i,1);
    }
    int pb;
    for (int i=0;i<nbSom;i++) {
        pb=0;
        for (int j=0;j<nbSom;j++) {
            if (memo[i][j][0]==1) {
                pb=1;
            }
        }
        if (pb==0) {
            poliCour=i;
            return i;
        }
    }
    return -1;
}

int nextMove(int posVol) {
    int ans=suiv[poliCour][posVol];
    poliCour=ans;
    return ans;
}

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