結果
問題 | No.1605 Matrix Shape |
ユーザー |
![]() |
提出日時 | 2021-07-20 15:53:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,936 bytes |
コンパイル時間 | 1,150 ms |
コンパイル使用メモリ | 104,116 KB |
実行使用メモリ | 19,400 KB |
最終ジャッジ日時 | 2024-07-17 13:42:58 |
合計ジャッジ時間 | 4,903 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
/* -*- 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; } printf("%d\n", (stc > 0) ? 1 : m); return 0; }