QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#516962 | #9170. Cycle Game | ucup-team1198# | AC ✓ | 94ms | 16964kb | C++14 | 4.0kb | 2024-08-13 01:51:21 | 2024-08-13 01:51:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 100;
int p[MAXN], sz[MAXN];
int get(int v) {
return v == p[v] ? v : p[v] = get(p[v]);
}
void join(int u, int v) {
u = get(u); v = get(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
p[v] = u;
}
vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};
int sample[3][3];
int col[3][3];
void dfs(int x, int y, int c) {
col[x][y] = c;
/// cerr << x << " " << y << "->" << c << endl;
for (int t = 0; t < 4; ++t) {
int x1 = x + dx[t], y1 = y + dy[t];
if (x1 < 0 || x1 >= 3 || y1 < 0 || y1 >= 3 || sample[x1][y1] == 0) continue;
if (col[x1][y1] == -1) {
dfs(x1, y1, c);
}
}
}
void solve_() {
int n, m, k;
cin >> n >> m >> k;
iota(p, p + n * m, 0);
fill(sz, sz + n * m, 1);
vector<vector<int>> arr(n, vector<int>(m, 0));
while (k--) {
int i, j;
cin >> i >> j;
--i; --j;
if (arr[i][j] == 1) {
cout << "1";
continue;
}
arr[i][j] = 1;
bool simple = true;
for (int sx = i - 2; sx <= i && simple; ++sx) {
for (int sy = j - 2; sy <= j && simple; ++sy) {
if (sx < 0 || sy < 0 || sx + 3 > n || sy + 3 > m) continue;
bool cur = false;
for (int x = 0; x < 3 && !cur; ++x) {
for (int y = 0; y < 3 && !cur; ++y) {
cur |= (arr[sx + x][sy + y] == 0);
}
}
simple &= cur;
}
}
arr[i][j] = 0;
if (!simple) {
cout << "0";
continue;
}
vector<array<int, 2>> neigh;
for (int t = 0; t < 4; ++t) {
int x = i + dx[t];
int y = j + dy[t];
if (x < 0 || y < 0 || x >= n || y >= m || arr[x][y] == 0) continue;
neigh.push_back({x, y});
}
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
int x = i + dx, y = j + dy;
if (x < 0 || y < 0 || x >= n || y >= m || arr[x][y] == 0) {
sample[dx + 1][dy + 1] = 0;
} else {
sample[dx + 1][dy + 1] = 1;
}
col[dx + 1][dy + 1] = -1;
}
}
int c = 0;
for (auto elem : neigh) {
if (col[elem[0] - i + 1][elem[1] - j + 1] == -1) {
dfs(elem[0] - i + 1, elem[1] - j + 1, c++);
}
}
/**if (i == 1 && j == 3) {
for (int x = 0; x < 3; ++x) {
for (int y = 0; y < 3; ++y) {
cerr << sample[x][y] << " ";
}
cerr << endl;
}
}*/
bool hard = true;
for (auto elem1 : neigh) {
for (auto elem2 : neigh) {
/**if (i == 2 && j == 1) {
cerr << elem1[0] << " " << elem1[1] << " " << elem2[0] << " " << elem2[1] << endl;
}*/
if (get(elem1[0] * m + elem1[1]) == get(elem2[0] * m + elem2[1])) {
if (col[elem1[0] - i + 1][elem1[1] - j + 1] != col[elem2[0] - i + 1][elem2[1] - j + 1]) {
/// cerr << i << " " << j << " " << elem1[0] << " " << elem1[1] << " " << elem2[0] << " " << elem2[1] << endl;
hard = false;
}
}
}
}
if (!hard) {
cout << "0";
continue;
}
cout << "1";
for (auto elem : neigh) {
join(i * m + j, elem[0] * m + elem[1]);
}
arr[i][j] = 1;
}
}
/// #define MULTITEST
main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tst = 1;
#ifdef MULTITEST
cin >> tst;
#endif // MULTITEST
while (tst--) {
solve_();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
4 3 7 2 1 2 2 2 3 3 1 3 2 4 1 4 2
output:
1111111
result:
ok "1111111"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 3 8 1 1 1 2 1 3 2 3 3 3 3 2 3 1 2 1
output:
11111110
result:
ok "11111110"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
10 10 7 9 1 6 6 3 8 8 7 5 10 1 7 1 2
output:
1111111
result:
ok "1111111"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
9 10 50 1 9 1 6 2 3 3 1 7 4 9 4 1 3 2 5 9 2 7 9 5 6 8 10 9 5 5 5 4 10 9 7 5 9 3 2 4 5 1 1 4 7 3 6 2 8 4 3 8 6 5 10 4 8 5 4 7 2 9 6 4 2 7 8 5 2 3 5 9 1 6 1 1 5 9 9 5 8 6 3 8 8 8 4 7 7 7 1 3 7 2 2 3 10 6 9 8 3 7 6
output:
11111111111111111111111111111111111111111111111111
result:
ok "11111111111111111111111111111111111111111111111111"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 5 11 1 5 2 4 1 2 1 3 3 3 3 1 3 4 2 3 1 4 2 1 2 5
output:
11111111111
result:
ok "11111111111"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
7 9 12 7 3 2 3 6 2 2 2 4 2 2 8 5 7 4 4 6 8 2 7 7 2 1 9
output:
111111111111
result:
ok "111111111111"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
1 4 1 1 2
output:
1
result:
ok "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
9 8 67 5 5 8 3 9 5 7 4 5 1 9 3 4 2 2 5 1 7 7 8 7 2 8 5 6 1 8 8 4 4 5 4 1 5 3 4 6 7 2 3 3 7 5 7 2 4 2 7 1 3 7 3 2 8 6 6 6 2 6 3 7 5 9 6 7 6 3 6 1 1 6 4 3 1 5 3 8 7 2 1 4 1 8 4 8 6 3 5 5 8 1 6 1 2 4 6 9 4 1 4 3 3 4 8 8 1 4 7 9 8 3 8 6 5 6 8 3 2 2 2 7 1 9 2 4 3 1 8 4 5 8 2 7 7
output:
1111111111111111111111111111111111111111111110010101101000101101101
result:
ok "111111111111111111111111111111...1111111110010101101000101101101"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
3 10 3 3 9 2 5 2 7
output:
111
result:
ok "111"
Test #10:
score: 0
Accepted
time: 9ms
memory: 16964kb
input:
222212 1 21562 105762 1 167947 1 127551 1 117618 1 174844 1 139867 1 156729 1 30554 1 54488 1 151832 1 132914 1 109432 1 212091 1 136499 1 17818 1 48806 1 95752 1 66607 1 39930 1 23054 1 160823 1 169054 1 96680 1 150677 1 52895 1 93103 1 118079 1 79155 1 194811 1 141874 1 138763 1 2600 1 121471 1 17...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #11:
score: 0
Accepted
time: 24ms
memory: 5744kb
input:
1 167058 126088 1 15282 1 63796 1 77270 1 88793 1 42787 1 129851 1 34468 1 74525 1 121105 1 157182 1 92736 1 102044 1 11284 1 23439 1 142720 1 128610 1 27437 1 105575 1 130827 1 152824 1 76358 1 152954 1 65509 1 139802 1 66299 1 108943 1 140446 1 112411 1 95814 1 115750 1 9667 1 55383 1 89323 1 6734...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #12:
score: 0
Accepted
time: 21ms
memory: 4868kb
input:
9 12788 86384 4 11931 2 8183 1 5816 7 10320 8 5754 4 10778 4 12280 7 12746 1 4699 3 7876 4 3044 2 4903 9 10252 8 10512 7 6546 8 1338 5 9700 1 9833 6 11315 2 4067 7 9350 9 8200 2 1718 1 2542 2 4596 9 367 5 12426 1 12166 5 7652 4 2316 9 1946 3 6187 4 3306 1 63 8 4132 3 12491 2 3951 8 4169 7 11801 9 46...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0010111100011000000100110101100"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
10 6 58 7 3 1 5 9 2 10 4 1 2 1 6 9 6 5 4 8 2 9 3 5 1 4 5 7 4 10 1 10 3 5 3 4 3 6 5 1 4 7 2 10 6 8 3 5 6 9 4 2 2 1 1 6 4 3 5 3 2 6 2 3 6 8 1 8 4 8 5 7 5 6 1 4 4 3 4 3 1 7 1 4 1 2 4 6 6 9 5 7 6 2 1 5 5 10 2 2 5 4 2 2 6 10 5 9 1 4 6 5 2 6 3 1 3 8 6
output:
1111111111111111111111111111111101111111111011011001000000
result:
ok "1111111111111111111111111111111101111111111011011001000000"
Test #14:
score: 0
Accepted
time: 0ms
memory: 4852kb
input:
23660 2 4698 10158 1 1229 1 51 2 10559 2 15495 2 19343 1 18458 1 19633 2 23151 1 11738 2 21366 1 12968 2 10474 1 10552 2 8067 2 7125 2 14643 1 7579 2 21608 2 7067 2 20400 1 14397 2 21474 2 8294 2 1332 1 18105 1 2285 1 1223 1 13429 2 18580 2 11156 2 5498 1 6830 1 8848 2 21334 2 11946 1 10177 1 5349 1...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #15:
score: 0
Accepted
time: 9ms
memory: 3956kb
input:
51 732 29706 14 458 6 600 18 452 43 262 24 685 51 192 14 248 50 672 16 65 45 191 25 196 1 447 4 574 32 493 16 100 39 715 17 397 37 644 32 580 32 622 22 160 20 694 29 120 30 302 7 283 18 290 51 420 20 553 42 681 11 724 26 528 50 497 46 500 3 534 36 58 42 167 18 534 1 654 50 276 37 386 19 649 14 41 8 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0100001111101110110110000010000"
Test #16:
score: 0
Accepted
time: 66ms
memory: 9580kb
input:
75000 4 225000 71753 3 13211 2 61737 3 59039 3 3674 3 50461 4 12758 3 69966 1 57525 1 42178 1 15054 1 66939 2 2798 4 74983 2 7250 2 2247 4 11438 1 67858 4 66527 2 21625 2 14111 2 28737 1 7431 4 11317 3 47421 2 51295 4 39591 4 20811 3 51582 3 47874 2 3238 2 10987 3 1225 1 58741 4 2141 3 35454 4 5021 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1101011111100100010101000000000"
Test #17:
score: 0
Accepted
time: 64ms
memory: 11016kb
input:
100000 3 240000 63826 2 25561 1 24122 3 56762 3 66822 2 24467 2 5419 1 59533 2 71406 2 62274 1 63084 1 33262 3 16614 2 71724 1 99182 1 3574 3 2804 2 40022 2 90379 1 44898 2 59169 3 55663 1 79971 2 30606 3 58613 3 38992 3 51702 1 10168 3 44411 3 39048 1 25384 2 276 1 68607 1 34137 1 72641 2 92427 1 9...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0101001000001000101001011110010"
Test #18:
score: 0
Accepted
time: 79ms
memory: 8972kb
input:
60000 5 250000 19905 3 6687 2 7727 4 23854 3 1329 4 45419 4 15116 1 35612 4 11560 1 16969 5 43328 4 30175 2 1587 5 15890 1 53896 3 43465 4 26642 2 3443 5 6697 5 6489 3 44351 2 48037 2 39926 5 974 1 20783 2 51437 4 31394 2 33663 2 26261 5 49301 4 2074 1 16999 4 48098 5 28754 4 27961 3 614 5 57608 2 5...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0010100101111000100000011001011"
Test #19:
score: 0
Accepted
time: 79ms
memory: 11072kb
input:
100000 3 270000 50999 2 78476 3 21423 1 26134 3 69234 1 48259 3 40043 1 92586 1 96544 3 65679 1 63139 1 79464 2 76129 3 3836 3 65093 1 81997 3 13905 2 82341 2 32201 1 42796 2 69216 3 14753 3 50176 3 66724 2 21607 3 9619 2 96579 1 59856 2 5086 1 89747 1 4122 3 8806 3 57529 2 6476 3 6689 2 97261 1 936...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0000011010000000010100010001010"
Test #20:
score: 0
Accepted
time: 90ms
memory: 7532kb
input:
29997 10 272700 22251 10 4359 10 3780 4 23168 10 19310 8 784 2 21855 1 19914 4 279 9 26868 6 11534 3 17252 8 10865 2 15782 3 10134 4 17047 4 8318 5 11552 4 21333 1 2023 10 17397 5 13151 3 21068 3 1171 3 21112 4 23374 4 289 8 9248 3 19337 3 10005 7 16909 2 14103 5 3098 8 23534 3 7782 1 4765 7 10294 8...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1100000010000000010000000100010"
Test #21:
score: 0
Accepted
time: 35ms
memory: 7652kb
input:
30000 10 180008 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111110111111101111111011111111"
Test #22:
score: 0
Accepted
time: 45ms
memory: 10932kb
input:
100000 3 250001 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0000000000000000000000000000001"
Test #23:
score: 0
Accepted
time: 27ms
memory: 6864kb
input:
300 1000 151298 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 ...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...1111111111111111111111111111111"
Test #24:
score: 0
Accepted
time: 88ms
memory: 6720kb
input:
1000 300 300000 1 1 1 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1 19 1 21 1 23 1 25 1 27 1 29 1 31 1 33 1 35 1 37 1 39 1 41 1 43 1 45 1 47 1 49 1 51 1 53 1 55 1 57 1 59 1 61 1 63 1 65 1 67 1 69 1 71 1 73 1 75 1 77 1 79 1 81 1 83 1 85 1 87 1 89 1 91 1 93 1 95 1 97 1 99 1 101 1 103 1 105 1 107 1 109 1 111 1 1...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0000001001001100100000110100001"
Test #25:
score: 0
Accepted
time: 94ms
memory: 7516kb
input:
30000 10 300000 1 1 1 3 1 5 1 7 1 9 3 1 3 3 3 5 3 7 3 9 5 1 5 3 5 5 5 7 5 9 7 1 7 3 7 5 7 7 7 9 9 1 9 3 9 5 9 7 9 9 11 1 11 3 11 5 11 7 11 9 13 1 13 3 13 5 13 7 13 9 15 1 15 3 15 5 15 7 15 9 17 1 17 3 17 5 17 7 17 9 19 1 19 3 19 5 19 7 19 9 21 1 21 3 21 5 21 7 21 9 23 1 23 3 23 5 23 7 23 9 25 1 25 3...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok "111111111111111111111111111111...0001000000000000100000000010000"
Extra Test:
score: 0
Extra Test Passed