#include "coprobber.h"
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define fr first
#define mp make_pair
#define sc second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define vec vector
#define TURBO {ios::sync_with_stdio(0); cin.tie(0);}
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pair<int, int>>;
using vvi = vector<vi>;
int go[MAX_N][MAX_N];
int win[MAX_N][MAX_N][2];
int cop;
class directed_graph{
public:
int N;
vector<vector<vector<vector<pair<pii,int>>>>>adj, comp;
directed_graph(int _N): N(_N){
adj.resize(N);
comp.resize(N);
for (int i = 0; i < N; i++){
adj[i].resize(N);
comp[i].resize(N);
for (int j = 0; j < N; j++){
adj[i][j].resize(2);
comp[i][j].resize(2);
}
}
}
void add_edge(int c, int r, int t, int c1, int r1, int t1){
comp[c][r][t].pb(mp(mp(c1,r1),t1));
adj[c1][r1][t1].pb(mp(mp(c,r),t));
}
void Bredth_First_Search(int c0, int r0, int t0){
queue<pair<pii,int>>q;
q.push(mp(mp(c0,r0),t0));
int visited[N][N][2];
memset(visited,0,sizeof(visited));
visited[c0][r0][t0] = 1;
while(!q.empty()){
auto node = q.front();
q.pop();
win[node.fr.fr][node.fr.sc][node.sc] = 1;
each(x,adj[node.fr.fr][node.fr.sc][node.sc]){
if (visited[x.fr.fr][x.fr.sc][x.sc])continue;
visited[x.fr.fr][x.fr.sc][x.sc] = 1;
q.push(x);
}
}
}
void Condense(bool A[][MAX_N]){
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
bool forced = 1;
for (int k = 0; k < N; k++){
if (A[i][k]){
forced &= (win[j][k][0]);
}
}
win[j][i][1] = forced;
}
}
}
void Build_strategy(){
for (int c = 0; c < N; c++){
for(int r = 0; r < N; r++){
if (win[c][r][0]){
each(x,comp[c][r][0]){
if (win[x.fr.fr][x.fr.sc][x.sc]){
go[c][r] = x.fr.fr;
break;
}
}
}
}
}
}
};
int start(int N, bool A[MAX_N][MAX_N])
{
directed_graph G(N);
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
for (int k = 0; k < N; k++){
if (A[i][k])
G.add_edge(i,j,0,k,j,1);
if (A[j][k])
G.add_edge(i,j,1,i,k,0);
}
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
if (i == j){
G.Bredth_First_Search(i,j,0);
G.Bredth_First_Search(i,j,1);
}
if (A[i][j]){
G.Bredth_First_Search(i,j,0);
}
}
}
G.Condense(A);
G.Build_strategy();
for (int i = 0; i < N; i++){
bool ok = 1;
for (int j = 0; j < N; j++){
ok &= win[i][j][0];
}
if (ok){
cop = i;
return i;
}
}
return -1;
}
int nextMove(int R)
{
cop = go[cop][R];
return cop;;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
the situation repeated |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
the situation repeated |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
the situation repeated |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
the situation repeated |
| 4 |
Halted |
0 ms |
0 KB |
- |
