結果
問題 |
No.1605 Matrix Shape
|
ユーザー |
![]() |
提出日時 | 2021-12-29 19:20:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 583 ms / 2,000 ms |
コード長 | 1,822 bytes |
コンパイル時間 | 1,721 ms |
コンパイル使用メモリ | 182,872 KB |
実行使用メモリ | 34,476 KB |
最終ジャッジ日時 | 2024-10-04 08:01:47 |
合計ジャッジ時間 | 9,866 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct UnionFind{ vector<int> parent; vector<int> numberOfElements;//根ノードのみ有効 UnionFind(int n){ parent.resize(n); numberOfElements.resize(n); for(int i=0;i<n;++i){ parent[i]=-1; numberOfElements[i]=1; } } int find(int a){ vector<int> path(0); int pointer=a; while(parent[pointer]!=-1){ path.push_back(pointer); pointer=parent[pointer]; } for(int i:path){ parent[i]=pointer; } return pointer; } void unite(int a,int b){ int p=find(a); int q=find(b); if(p==q){ return; } if(numberOfElements[p]<numberOfElements[q]){ parent[p]=q; numberOfElements[q]+=numberOfElements[p]; }else{ parent[q]=p; numberOfElements[p]+=numberOfElements[q]; } } }; int main(){ int N,temp=0,check=0; cin>>N; map<int,int> cnt; vector<vector<int>> a(N,vector<int>(2)); for(int i=0;i<N;++i){ for(int j=0;j<2;++j){ cin>>a[i][j]; cnt[a[i][j]]+=j*2-1; } } int p=cnt.size(); map<int,int> comp; for(auto i=cnt.begin();i!=cnt.end();++i){ comp[i->first]=temp; ++temp; check+=abs(i->second); } UnionFind U(p); for(vector<int> v:a){ U.unite(comp[v[0]],comp[v[1]]); } temp=U.find(comp[a[0][0]]); for(auto i=cnt.begin();i!=cnt.end();++i){ if(U.find(comp[i->first])!=temp){ cout<<0<<endl; return 0; } } if(check>2){ cout<<0<<endl; }else if(check){ cout<<1<<endl; }else{ cout<<p<<endl; } }