| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 155438 | oolimry | 경찰관과 강도 (BOI14_coprobber) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
static int states[500005]; //police * 1000 + robber * 2 + (IF POLICE TURN)
static int degree[500005];
static int to[500005];
static vector<int> rev[500005];
queue<int> can;
inline int g(int police, int robber, int turn){
return police * 1000 + robber * 2 + turn;
}
int pos;
int start(int N, bool A[MAX_N][MAX_N])
{
int n = N;
for(int u = 0;u < n;u++){
for(int v = 0;v < n;v++){
int s = g(u,v,0);
rev[s+1].push_back(s); //Wait
degree[s]++;
for(int i = 0;i < n;i++){
if(A[u][i] == 1){
rev[g(i,v,1)].push_back(s);
degree[s]++;
}
if(A[v][i] == 1){
rev[g(u,i,0)].push_back(s+1);
degree[s+1]++;
}
}
if(u == v){
states[s] = 1;
states[s+1] = 1;
}
}
}
for(int i = 0;i < 500005;i++){
if(states[i] == 1){
can.push(i);
degree[i] = 0;
}
}
int work[n];
fill(work,work+n,n);
while(!can.empty()){
int t = can.front();
//cout << t << "\n";
if(!(t&1)){
work[t/1000]--;
if(work[t/1000] == 0){
pos = t/1000;
return t/1000;
}
}
can.pop();
for(int i = 0;i < rev[t].size();i++){
int s = rev[t][i];
if(states[s] == 0){
degree[s]--;
//cout << t << " " << s << " " << degree[s] << "\n";
if(!(s & 1)){
can.push(s);
states[s] = 1;
degree[s] = 0;
to[s] = t;
//cout << s << " " << t << "\n";
}
else if(degree[s] == 0){
can.push(s);
states[s] = 1;
}
}
}
}
return -1;
}