이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
const int MAX_N = 500;
int nx[2][MAX_N][MAX_N];
std::vector<int> G[2][MAX_N][MAX_N];
int cc[2][MAX_N][MAX_N];
int Pu = 0;
struct Dat {
int x;
Dat(int m, int p, int r) {
x = m; // [0, 0]
x |= p << 1; // [1, 9]
x |= r << 10; // [10, 18]
}
int getM() const {
return x & 1;
}
int getR() const {
return x >> 10;
}
int getP() const {
return (x >> 1) & 511; // 511 = 2**9 - 1
}
void set(int& m, int& p, int& r) const {
m = getM();
p = getP();
r = getR();
}
};
void bfs(int N, bool A[MAX_N][MAX_N]) {
std::memset(nx, -1, sizeof nx);
for(int r = 0; r < N; r++) {
int deg = std::count(A[r], A[r] + N, true);
for(int p = 0; p < N; p++) {
cc[0][p][r] = 1;
cc[1][p][r] = deg;
}
}
std::queue<Dat> q;
for(int p = 0; p < N; p++) {
cc[0][p][p] = cc[1][p][p] = 0;
q.push(Dat(0, p, p)); q.push(Dat(1, p, p));
nx[0][p][p] = nx[1][p][p] = p;
}
while(!q.empty()) {
int m, p, r; q.front().set(m, p, r);
//if(m == 0) std::cerr << (m == 0 ? 'P' : 'R') << " " << p << " " << r << "\n";
q.pop();
if(m == 0) {
for(int v = 0; v < N; v++) {
if(!A[r][v] || cc[1][p][v] == 0) continue;
const int m1 = 1, p1 = p, r1 = v;
cc[m1][p1][r1]--;
if(cc[m1][p1][r1] == 0) {
nx[m1][p1][r1] = r;
q.push(Dat(m1, p1, r1));
}
}
} else {
for(int v = 0; v < N; v++) {
if(!A[p][v] || cc[0][v][r] == 0) continue;
const int m1 = 0, p1 = v, r1 = r;
cc[m1][p1][r1] = 0;
nx[m1][p1][r1] = p;
q.push(Dat(m1, p1, r1));
}
if(cc[0][p][r]) {
cc[0][p][r] = 0;
nx[0][p][r] = p;
q.push(Dat(0, p, r));
}
}
}
}
int add[2][MAX_N], ii = 0, jj = 0;
int start(int N, bool A[MAX_N][MAX_N]) {
bfs(N, A);
for(int r = 0; r < N; r++) {
if(nx[0][0][r] == -1 || cc[0][0][r] > 0) {
//std::cerr << "bad " << r << std::endl;
return -1;
}
}
return Pu = 0;
}
int nextMove(int R) {
Pu = nx[0][Pu][R];
return Pu;
}
//#define DEBUG
#ifdef DEBUG
// don't modify the main function
int main() {
int N;
std::cin >> N;
bool A[MAX_N][MAX_N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
std::cin >> A[i][j];
}
}
int P = start(N,A);
std::cout << P << std::endl;
//std::exit(0);
int R;
std::cin >> R;
while (true) {
if (P == R) break;
P = nextMove(R);
std::cout << P << std::endl;
if (P == R) break;
std::cin >> R;
}
}
#endif
# | 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... |