結果
問題 | No.1605 Matrix Shape |
ユーザー | tnakao0123 |
提出日時 | 2021-07-20 15:44:00 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,020 bytes |
コンパイル時間 | 1,248 ms |
コンパイル使用メモリ | 106,560 KB |
実行使用メモリ | 19,400 KB |
最終ジャッジ日時 | 2024-07-17 13:42:44 |
合計ジャッジ時間 | 6,501 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
11,848 KB |
testcase_01 | AC | 4 ms
9,800 KB |
testcase_02 | AC | 4 ms
11,848 KB |
testcase_03 | AC | 4 ms
11,852 KB |
testcase_04 | AC | 4 ms
9,800 KB |
testcase_05 | AC | 4 ms
9,924 KB |
testcase_06 | AC | 4 ms
11,976 KB |
testcase_07 | AC | 4 ms
11,844 KB |
testcase_08 | WA | - |
testcase_09 | AC | 4 ms
11,720 KB |
testcase_10 | AC | 4 ms
9,796 KB |
testcase_11 | AC | 3 ms
9,796 KB |
testcase_12 | WA | - |
testcase_13 | AC | 4 ms
9,792 KB |
testcase_14 | AC | 3 ms
9,800 KB |
testcase_15 | AC | 4 ms
9,796 KB |
testcase_16 | AC | 4 ms
9,792 KB |
testcase_17 | AC | 4 ms
11,724 KB |
testcase_18 | AC | 4 ms
11,720 KB |
testcase_19 | AC | 236 ms
19,400 KB |
testcase_20 | WA | - |
testcase_21 | AC | 165 ms
15,816 KB |
testcase_22 | AC | 192 ms
19,144 KB |
testcase_23 | WA | - |
testcase_24 | AC | 202 ms
19,396 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 84 ms
13,644 KB |
testcase_28 | AC | 85 ms
13,000 KB |
testcase_29 | AC | 86 ms
12,736 KB |
testcase_30 | WA | - |
testcase_31 | AC | 159 ms
15,812 KB |
testcase_32 | WA | - |
testcase_33 | AC | 137 ms
14,540 KB |
testcase_34 | AC | 57 ms
12,324 KB |
testcase_35 | AC | 130 ms
17,476 KB |
testcase_36 | AC | 77 ms
15,304 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 1605.cc: No.1605 Matrix Shape - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200000; const int MAX_M = 200000; /* typedef */ typedef vector<int> vi; typedef queue<int> qi; typedef pair<int,int> pii; /* global variables */ pii ps[MAX_N]; vi nbrs[MAX_M]; int xs[MAX_N * 2], ies[MAX_M], oes[MAX_M]; bool used[MAX_M]; /* subroutines */ int bfd(int st) { used[st] = true; int c = 1; qi q; q.push(st); while (! q.empty()) { int u = q.front(); q.pop(); for (auto v: nbrs[u]) if (! used[v]) { used[v] = true; c++; q.push(v); } } return c; } /* main */ int main() { int n; scanf("%d", &n); int m = 0; for (int i = 0; i < n; i++) { int h, w; scanf("%d%d", &h, &w); h--, w--; ps[i] = pii(h, w); xs[m++] = h, xs[m++] = w; } sort(xs, xs + m); m = unique(xs, xs + m) - xs; //printf("m=%d\n", m); for (int i = 0; i < n; i++) { int hi = lower_bound(xs, xs + m, ps[i].first) - xs; int wi = lower_bound(xs, xs + m, ps[i].second) - xs; ps[i] = pii(hi, wi); ies[wi]++, oes[hi]++; nbrs[hi].push_back(wi); } int stc = 0, glc = 0, sti = -1, gli = -1;; for (int i = 0; i < m; i++) { if (ies[i] + 1 == oes[i]) stc++, sti = i; else if (oes[i] + 1 == ies[i]) glc++, gli = i; else if (ies[i] != oes[i]) { puts("0"); return 0; } } if (stc > 1 || glc > 1 || stc != glc) { puts("0"); return 0; } int c = bfd((stc > 0) ? sti : 0); //printf("c=%d, m=%d\n", c, m); if (c < m) { puts("0"); return 0; } if (stc > 0) puts("1"); else { sort(ps, ps + n); n = unique(ps, ps + n) - ps; printf("%d\n", n); } return 0; }