# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77323 | Charis02 | Cop and Robber (BOI14_coprobber) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "coprobber.h"
#include<iostream>
#include<vector>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAX_N 505
#define ll long long
using namespace std;
bool can[MAX_N][MAX_N][2],vis[MAX_N][MAX_N][2];
vector < vector < ll > > graph(MAX_N);
ll curcop;
bool solve(ll cop,ll rob,ll who) // who = 0 -> cop, who = 1 -> robber
{
if(cop == rob)
return (who == 0);
vis[cop][rob][who] = true;
if(who == 0)
{
rep(i,0,graph[cop].size())
{
if(!vis[graph[cop][i]][rob][1] && !solve(graph[cop][i],rob,1))
{
vis[cop][rob][who] = false;
return true;
}
}
vis[cop][rob][who] = false;
return false;
}
rep(i,0,graph[rob].size())
{
if(vis[cop][graph[rob][i]][0])
{
vis[cop][rob][who] = false;
return true;
}
}
vis[cop][rob][who] = false;
return false;
}
int start(int N, bool A[MAX_N][MAX_N])
{
rep(i,0,N)
{
rep(j,0,N)
{
if(A[i][j])
graph[i].push_back(j);
}
}
rep(i,0,N)
{
curcop = i;
bool res = true;
rep(j,0,N)
{
if(solve(i,j,1))
{
res = false;
}
}
if(res)
return curcop = i;
}
return -1;
}
int nextMove(int R)
{
rep(i,0,graph[curcop].size())
{
if(solve(graph[curcop][i],R,0))
return graph[curcop][i];
}
}
/*
int main()
{
int n;
cin >> n;
bool a[MAX_N][MAX_N];
rep(i,0,n)
{
rep(j,0,n)
{
cin >> a[i][j];
}
}
cout<<start(n,a) << endl;
while(true)
{
int x;
cin >> x;
cout << nextMove(x) << endl;
}
}
*/