| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 479942 | gmyu | 경찰관과 강도 (BOI14_coprobber) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/BOI14_coprobber
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 507
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
bool debug;
//#include "coprobber.h"
typedef array<int, 3> T;
/** define state as (cop location, robber location, who's move now) = (c, r, t)
* an initial winning state is c == r. From a winning state,
* if it is cop's move now (as a winning state), then a robber should not come to this state.
* I.e., when it is a robber's move at (c,k,robber) where k <-> r are connected, the oppounity where k can go is reduced by 1
* if k has nowhere to go, then (c,k,robber) is a winning state
* if it is robber's move (as a winning state), the cop wants to come to this state
* i.e. if k <->c are connected, (k,r,cop) is a winning state
* if the total count of such state is 2 N^2, then regardless where robber is, it will be caught.
*/
int robberEscapeCnt[MAXV][MAXV];
int copVisited[MAXV][MAXV];
int copGoto[MAXV][MAXV];
#define MAX_N 507
int start(int N, bool A[MAX_N][MAX_N]) {
// count # of escape for robber at each state (c, r). I.e. how many k is connected to r
for(int i=0; i<N; i++) {
int ways=0;
for(int k=0;k<N;k++)
if(A[i][k]) ways++;
for(int c=0; c<N; c++)
if(c!=i) robberEscapeCnt[c][i] = ways;
}
queue<T> q;
for(int i=0; i<N; i++){
q.push({i,i,0});
q.push({i,i,1});
}
int cnt = 0;
while(!q.empty()) {
auto x = q.front(); q.pop();
cnt++;
if(x[2]==0) { // the move is cop
for(int k=0; k<N; k++) {
if(A[x[1]][k] && robberEscapeCnt[x[0]][k]) {
robberEscapeCnt[x[0]][k]--;
if(robberEscapeCnt[x[0]][k]==0) q.push({x[0], k, 1});
}
}
} else { // robber's move
for(int k=0; k<N; k++) {
if(k==x[0] || (A[x[0]][k] && !copVisited[k][x[1]])) {
q.push({k,x[1],0});
copVisited[k][x[1]]=1;
copGoto[k][x[1]] = x[0];
}
}
}
}
if(cnt == 2*N*N) return 0;
return -1;
}
int nxt = 0;
int nextMove(int robber) {
nxt = copGoto[nxt][robber];
return nxt;
}
/*
int main() {
debug = true;
ios_base::sync_with_stdio(false); cin.tie(0);
if(debug) cout << endl << "EOL" << endl;
}
*/