이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
const int MAX_N = 500;
// modify the following functions
// you can define global variables and functions
int nx[2][MAX_N][MAX_N];
std::vector<std::tuple<int,int,int>> G[2][MAX_N][MAX_N];
int cc[2][MAX_N][MAX_N];
int Pu = 0;
void bfs(int N, bool A[MAX_N][MAX_N]) {
std::memset(nx, -1, sizeof nx);
for(int p = 0; p < N; p++) {
for(int r = 0; r < N; r++) {
cc[0][p][r] = 1;
cc[1][p][r] = 0;
for(int v = 0; v < N; v++) {
if(A[r][v]) cc[1][p][r]++;
}
}
}
std::queue<std::tuple<int,int,int>> q;
for(int p = 0; p < N; p++) {
cc[0][p][p] = cc[1][p][p] = 0;
q.push(std::make_tuple(0, p, p)); q.push(std::make_tuple(1, p, p));
nx[0][p][p] = nx[1][p][p] = p;
}
while(!q.empty()) {
int m, p, r; std::tie(m, p, r) = q.front();
//if(m == 0) std::cerr << (m == 0 ? 'P' : 'R') << " " << p << " " << r << "\n";
q.pop();
for(auto v : G[m][p][r]) {
int m1, p1, r1; std::tie(m1, p1, r1) = v;
cc[m1][p1][r1]--;
if(cc[m1][p1][r1] == 0) {
nx[m1][p1][r1] = m1 == 0 ? p : r;
q.push(std::make_tuple(m1, p1, r1));
}
}
}
}
int start(int N, bool A[MAX_N][MAX_N]) {
for(int p = 0; p < N; p++) {
for(int r = 0; r < N; r++) {
G[1][p][r].emplace_back(0, p, r);
for(int v = 0; v < N; v++) {
if(A[p][v]) {
G[1][p][r].emplace_back(0, v, r);
}
if(A[r][v]) {
G[0][p][r].emplace_back(1, p, v);
}
}
}
}
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;
}
/*
// 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;
}
}
*/
# | 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... |