#include "coprobber.h"
#include <bits/stdc++.h>
#define name ""
#define ll long long
#define ld long double
#define fi first
#define se second
#define pll pair < ll, ll >
#define pii pair < int, int >
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define SZE(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define lnode node * 2, l, (l + r) / 2
#define rnode node * 2 + 1, (l + r) / 2 + 1, r
using namespace std;
const ld EPS = 1e-9;
const int INF = 1e9 + 7;
const ll LINF = 1E18;
const int N = 500;
const ll MOD = 1e9 + 7;
const ll BASE = 2309;
using tiii = tuple < int, int, int >;
bool dp[2][N][N]; // 0 la can 1 la trom
int nxt[N][N], cnt[N][N], cur;
// int n, a[N][N];
int start(int n, bool a[N][N]) {
queue < tiii > heap;
for (int i = 0; i < n; i++) dp[0][i][i] = dp[1][i][i] = 1, heap.push({0, i, i}), heap.push({1, i, i});
for (int t = 0; t < n; t++)
for (int i = 0; i < n; i++) {
if (t == 0) for (int j = 0; j < n; j++) cnt[t][i] += a[i][j];
else cnt[t][i] = cnt[t - 1][i];
}
while (heap.size()) {
int ope, i, j; tie(ope, i, j) = heap.front(); heap.pop();
if (ope == 0) { // luot can
for (int pre = 0; pre < n; pre++) if (a[j][pre]) {
cnt[i][pre] --;
if (cnt[i][pre] == 0) {
dp[ope ^ 1][i][pre] = 1;
heap.push({ope ^ 1, i, pre});
}
}
}
else {
for (int pre = 0; pre < n; pre++) if ((i == pre || a[i][pre]) && !dp[ope ^ 1][pre][j]) {
dp[ope ^ 1][pre][j] = 1;
heap.push({ope ^ 1, pre, j});
nxt[pre][j] = i;
}
}
}
for (int i = 0; i < n; i++) {
bool th = 1;
for (int j = 0; j < n; j++) th &= dp[0][i][j];
if (th) return cur = i;
}
return -1;
}
int nextMove(int R) {
return cur = nxt[cur][R];
}
/*
int main() {
fast;
if(fopen(name".inp", "r")) {
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
//int t; cin >> t; while (t --) sol();
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) cin >> a[i][j];
cout << start();
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Correct |
0 ms |
2392 KB |
Output is correct |
4 |
Correct |
237 ms |
4340 KB |
Output is correct |
5 |
Correct |
33 ms |
3684 KB |
Output is correct |
6 |
Correct |
240 ms |
4468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
239 ms |
4432 KB |
Output is correct |
4 |
Correct |
236 ms |
4172 KB |
Output is correct |
5 |
Correct |
219 ms |
4144 KB |
Output is correct |
6 |
Correct |
244 ms |
4296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Correct |
0 ms |
2392 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2392 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
0 ms |
2392 KB |
Output is correct |
9 |
Correct |
1 ms |
2392 KB |
Output is correct |
10 |
Correct |
1 ms |
2804 KB |
Output is correct |
11 |
Correct |
2 ms |
2648 KB |
Output is correct |
12 |
Correct |
1 ms |
2392 KB |
Output is correct |
13 |
Correct |
1 ms |
2648 KB |
Output is correct |
14 |
Correct |
2 ms |
2760 KB |
Output is correct |
15 |
Correct |
1 ms |
2648 KB |
Output is correct |
16 |
Correct |
1 ms |
2648 KB |
Output is correct |
17 |
Correct |
6 ms |
2904 KB |
Output is correct |
18 |
Correct |
2 ms |
2648 KB |
Output is correct |
19 |
Correct |
0 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Correct |
0 ms |
2392 KB |
Output is correct |
4 |
Correct |
237 ms |
4340 KB |
Output is correct |
5 |
Correct |
33 ms |
3684 KB |
Output is correct |
6 |
Correct |
240 ms |
4468 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2392 KB |
Output is correct |
9 |
Correct |
239 ms |
4432 KB |
Output is correct |
10 |
Correct |
236 ms |
4172 KB |
Output is correct |
11 |
Correct |
219 ms |
4144 KB |
Output is correct |
12 |
Correct |
244 ms |
4296 KB |
Output is correct |
13 |
Correct |
1 ms |
2392 KB |
Output is correct |
14 |
Correct |
0 ms |
2392 KB |
Output is correct |
15 |
Correct |
0 ms |
2392 KB |
Output is correct |
16 |
Correct |
1 ms |
2392 KB |
Output is correct |
17 |
Correct |
1 ms |
2392 KB |
Output is correct |
18 |
Correct |
1 ms |
2392 KB |
Output is correct |
19 |
Correct |
1 ms |
2392 KB |
Output is correct |
20 |
Correct |
0 ms |
2392 KB |
Output is correct |
21 |
Correct |
1 ms |
2392 KB |
Output is correct |
22 |
Correct |
1 ms |
2804 KB |
Output is correct |
23 |
Correct |
2 ms |
2648 KB |
Output is correct |
24 |
Correct |
1 ms |
2392 KB |
Output is correct |
25 |
Correct |
1 ms |
2648 KB |
Output is correct |
26 |
Correct |
2 ms |
2760 KB |
Output is correct |
27 |
Correct |
1 ms |
2648 KB |
Output is correct |
28 |
Correct |
1 ms |
2648 KB |
Output is correct |
29 |
Correct |
6 ms |
2904 KB |
Output is correct |
30 |
Correct |
2 ms |
2648 KB |
Output is correct |
31 |
Correct |
0 ms |
2392 KB |
Output is correct |
32 |
Correct |
1 ms |
2392 KB |
Output is correct |
33 |
Correct |
0 ms |
2392 KB |
Output is correct |
34 |
Correct |
1 ms |
2392 KB |
Output is correct |
35 |
Correct |
235 ms |
4092 KB |
Output is correct |
36 |
Correct |
36 ms |
3308 KB |
Output is correct |
37 |
Correct |
243 ms |
4568 KB |
Output is correct |
38 |
Correct |
0 ms |
2392 KB |
Output is correct |
39 |
Correct |
1 ms |
2392 KB |
Output is correct |
40 |
Correct |
232 ms |
4520 KB |
Output is correct |
41 |
Correct |
235 ms |
4428 KB |
Output is correct |
42 |
Correct |
221 ms |
4112 KB |
Output is correct |
43 |
Correct |
245 ms |
4072 KB |
Output is correct |
44 |
Correct |
0 ms |
2392 KB |
Output is correct |
45 |
Correct |
1 ms |
2392 KB |
Output is correct |
46 |
Correct |
0 ms |
2392 KB |
Output is correct |
47 |
Correct |
1 ms |
2392 KB |
Output is correct |
48 |
Correct |
1 ms |
2496 KB |
Output is correct |
49 |
Correct |
2 ms |
2648 KB |
Output is correct |
50 |
Correct |
1 ms |
2392 KB |
Output is correct |
51 |
Correct |
1 ms |
2648 KB |
Output is correct |
52 |
Correct |
3 ms |
2648 KB |
Output is correct |
53 |
Correct |
1 ms |
2648 KB |
Output is correct |
54 |
Correct |
1 ms |
2648 KB |
Output is correct |
55 |
Correct |
6 ms |
2904 KB |
Output is correct |
56 |
Correct |
1 ms |
2648 KB |
Output is correct |
57 |
Correct |
3 ms |
2648 KB |
Output is correct |
58 |
Correct |
11 ms |
2904 KB |
Output is correct |
59 |
Correct |
18 ms |
2932 KB |
Output is correct |
60 |
Correct |
351 ms |
7248 KB |
Output is correct |
61 |
Correct |
67 ms |
3964 KB |
Output is correct |
62 |
Correct |
59 ms |
3740 KB |
Output is correct |
63 |
Correct |
353 ms |
5920 KB |
Output is correct |
64 |
Correct |
61 ms |
3676 KB |
Output is correct |
65 |
Correct |
429 ms |
6864 KB |
Output is correct |
66 |
Correct |
233 ms |
4868 KB |
Output is correct |
67 |
Correct |
405 ms |
5912 KB |
Output is correct |
68 |
Correct |
155 ms |
3504 KB |
Output is correct |
69 |
Correct |
0 ms |
2392 KB |
Output is correct |