이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
bool G[505][505][2];
int R[505][505];
int AD[505];
int n;
tuple<int,int,int> P[505][505][2];
// Game Theory
// G[i][j][0] wins if there is a k such that G[k][j][1] is winning
// G[i][j][1] wins if all k adjacence to j G[i][k][0] is true
int currA = 0 , currB = -1;
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
queue<tuple<int,int,int > > q;
for(int i = 0 ; i < N ; i++){
G[i][i][0] = 1;
G[i][i][1] = 1;
q.push(make_tuple(i,i,0));
q.push(make_tuple(i,i,1));
}
// fill R[][]
for(int i = 0 ; i < n; i++){
for(int j = 0 ; j < n; j ++){
for(int k = 0 ; k < n; k ++){
if(k == j) continue;
R[i][j] = R[i][j] + A[j][k];
}
}
}
while(!q.empty()){
tuple<int,int,int> u = q.front();
q.pop();
if(get<2>(u)){
for(int i = 0 ; i < n; i++){
if(A[i][get<0>(u)] || i == get<0>(u)){
if(G[i][get<1>(u)][0] == 0){
G[i][get<1>(u)][0] = 1;
tuple<int,int,int> t = u;
get<0>(t) = i, get<2>(t) = 0;
P[get<0>(t)][get<1>(t)][get<2>(t)] = u;
q.push(t);
}
}
}
}
else{
for(int i = 0 ; i < n; i ++){
if(A[i][get<1>(u)]){
R[get<0>(u)][i]--;
if(R[get<0>(u)][i] == 0){
G[get<0>(u)][i][1] = true;
tuple<int,int,int> t = u;
get<1>(t) = i;
get<2>(t) = 1;
P[get<0>(t)][get<1>(t)][get<2>(t)] = u;
//cout<< get<0>(u) <<" " << get<1>(u) <<" " << get<2>(u) << endl;
//cout<< get<0>(t) <<" " << get<1>(t) <<" " << get<2>(t) << endl;
q.push(t);
}
}
}
}
}
bool can = true;
for(int i = 0 ; i < n; i ++){
if(!G[0][i][0]) can = false;
}
if(can){
return 0;
}
else{
return -1;
}
}
int nextMove(int R)
{
currB = R;
tuple<int,int,int> L = P[currA][currB][0];
return currA = get<0>(L);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |