結果
問題 |
No.1605 Matrix Shape
|
ユーザー |
![]() |
提出日時 | 2021-07-17 00:01:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 1,739 bytes |
コンパイル時間 | 4,410 ms |
コンパイル使用メモリ | 237,888 KB |
実行使用メモリ | 16,640 KB |
最終ジャッジ日時 | 2024-07-06 11:36:57 |
合計ジャッジ時間 | 7,509 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include "bits/stdc++.h" #include "atcoder/all" using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; const int INF = 1e9; //const long long LINF = 1e18; //const bool debug = false; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" #define P pair<int,int> template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int>vh(n), vw(n); map<int, int>mp; rep(i, n) { int h, w; cin >> h >> w; if (0 == mp.count(h)) mp[h] = mp.size(); vh[i] = mp[h]; if (0 == mp.count(w)) mp[w] = mp.size(); vw[i] = mp[w]; } dsu uf(mp.size()); rep(i, n) uf.merge(vh[i], vw[i]); if (mp.size() != uf.size(0)) { cout << 0 << endl; return 0; } vector<int>in(mp.size()), out(mp.size()); rep(i, n) { out[vh[i]]++; in[vw[i]]++; } vector<int>v(3); rep(i, mp.size()) { //cout << out[i] << " " << in[i] << endl; int x = out[i] - in[i]; if (1 == x)v[0]++; else if (-1 == x)v[1]++; else if (0 == x)v[2]++; } if (mp.size() == v[2]) { cout << mp.size() << endl; } else if ((1 == v[0]) && (1 == v[1]) && ((mp.size() - 2) == v[2])) { cout << 1 << endl; } else { cout << 0 << endl; } return 0; }