#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 |
1 |
Correct |
14 ms |
14080 KB |
Output is correct |
2 |
Correct |
14 ms |
14080 KB |
Output is correct |
3 |
Correct |
14 ms |
14080 KB |
Output is correct |
4 |
Correct |
237 ms |
17400 KB |
Output is correct |
5 |
Correct |
47 ms |
15608 KB |
Output is correct |
6 |
Correct |
267 ms |
17404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14080 KB |
Output is correct |
2 |
Correct |
13 ms |
14080 KB |
Output is correct |
3 |
Correct |
235 ms |
17388 KB |
Output is correct |
4 |
Correct |
238 ms |
17400 KB |
Output is correct |
5 |
Correct |
232 ms |
17272 KB |
Output is correct |
6 |
Correct |
244 ms |
17280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
14080 KB |
Output is correct |
2 |
Correct |
13 ms |
14080 KB |
Output is correct |
3 |
Correct |
15 ms |
14080 KB |
Output is correct |
4 |
Correct |
13 ms |
14080 KB |
Output is correct |
5 |
Correct |
14 ms |
14080 KB |
Output is correct |
6 |
Correct |
14 ms |
14080 KB |
Output is correct |
7 |
Correct |
14 ms |
14080 KB |
Output is correct |
8 |
Correct |
15 ms |
14080 KB |
Output is correct |
9 |
Correct |
15 ms |
14080 KB |
Output is correct |
10 |
Correct |
15 ms |
14464 KB |
Output is correct |
11 |
Correct |
16 ms |
14464 KB |
Output is correct |
12 |
Correct |
14 ms |
14208 KB |
Output is correct |
13 |
Correct |
14 ms |
14336 KB |
Output is correct |
14 |
Correct |
15 ms |
14464 KB |
Output is correct |
15 |
Correct |
14 ms |
14336 KB |
Output is correct |
16 |
Correct |
14 ms |
14336 KB |
Output is correct |
17 |
Correct |
19 ms |
14720 KB |
Output is correct |
18 |
Correct |
14 ms |
14464 KB |
Output is correct |
19 |
Correct |
13 ms |
14080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
14080 KB |
Output is correct |
2 |
Correct |
13 ms |
14080 KB |
Output is correct |
3 |
Correct |
13 ms |
14036 KB |
Output is correct |
4 |
Correct |
236 ms |
17400 KB |
Output is correct |
5 |
Correct |
46 ms |
15616 KB |
Output is correct |
6 |
Correct |
268 ms |
17400 KB |
Output is correct |
7 |
Correct |
13 ms |
14080 KB |
Output is correct |
8 |
Correct |
13 ms |
14080 KB |
Output is correct |
9 |
Correct |
235 ms |
17352 KB |
Output is correct |
10 |
Correct |
243 ms |
17528 KB |
Output is correct |
11 |
Correct |
229 ms |
17272 KB |
Output is correct |
12 |
Correct |
245 ms |
17272 KB |
Output is correct |
13 |
Correct |
17 ms |
14080 KB |
Output is correct |
14 |
Correct |
13 ms |
14080 KB |
Output is correct |
15 |
Correct |
14 ms |
14052 KB |
Output is correct |
16 |
Correct |
13 ms |
14208 KB |
Output is correct |
17 |
Correct |
15 ms |
14464 KB |
Output is correct |
18 |
Correct |
16 ms |
14592 KB |
Output is correct |
19 |
Correct |
14 ms |
14208 KB |
Output is correct |
20 |
Correct |
14 ms |
14464 KB |
Output is correct |
21 |
Correct |
16 ms |
14468 KB |
Output is correct |
22 |
Correct |
14 ms |
14336 KB |
Output is correct |
23 |
Correct |
15 ms |
14344 KB |
Output is correct |
24 |
Correct |
20 ms |
14720 KB |
Output is correct |
25 |
Correct |
17 ms |
14592 KB |
Output is correct |
26 |
Correct |
17 ms |
14976 KB |
Output is correct |
27 |
Correct |
28 ms |
15872 KB |
Output is correct |
28 |
Correct |
37 ms |
16256 KB |
Output is correct |
29 |
Correct |
347 ms |
18808 KB |
Output is correct |
30 |
Correct |
92 ms |
16760 KB |
Output is correct |
31 |
Correct |
96 ms |
17016 KB |
Output is correct |
32 |
Correct |
451 ms |
18780 KB |
Output is correct |
33 |
Correct |
104 ms |
16940 KB |
Output is correct |
34 |
Correct |
616 ms |
18988 KB |
Output is correct |
35 |
Correct |
265 ms |
18296 KB |
Output is correct |
36 |
Correct |
552 ms |
18680 KB |
Output is correct |
37 |
Correct |
256 ms |
16888 KB |
Output is correct |
38 |
Correct |
14 ms |
14080 KB |
Output is correct |