Submission #479943

#	Time	Username	Problem	Language	Result	Execution time	Memory
479943		gmyu	Cop and Robber (BOI14_coprobber)	C++14	0 / 100	0 ms	328 KiB

coprobber

/*
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;

}
*/

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