結果
問題 |
No.2291 Union Find Estimate
|
ユーザー |
|
提出日時 | 2023-07-25 12:40:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 449 ms / 2,000 ms |
コード長 | 2,990 bytes |
コンパイル時間 | 1,279 ms |
コンパイル使用メモリ | 117,112 KB |
最終ジャッジ日時 | 2025-02-15 18:54:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<61; typedef pair<int,int> P; typedef pair<int,P> PP; const ll MOD=998244353; class UnionFind{ public: std::vector<int> par; std::vector<int> rank; std::vector<int> sz;//sz[i]で,頂点iが含まれているグループのサイズ std::vector<int> root; UnionFind(int size){ rank=std::vector<int>(size+1,0); par = std::vector<int>(size+1,0); std::iota(par.begin(),par.end(),0);//#include<numeric> sz = std::vector<int>(size+1,1); root=std::vector<int>(size+1); std::iota(root.begin(),root.end(),0); } ~UnionFind(){ std::vector<int>().swap(rank); std::vector<int>().swap(par); std::vector<int>().swap(sz); std::vector<int>().swap(root); } int find(int x){ if(par[x]==x)return x; else return par[x] = find(par[x]); } bool issame(int u,int v){ return find(u)==find(v); } void merge(int u,int v){ u = find(u); v = find(v); if(u==v) return; if(rank[u]<rank[v]) std::swap(u,v); //uの傘下へvが入る //rank[u]>=rank[v] par[v]=u; sz[u]+=sz[v]; if(rank[u]==rank[v])rank[u]++; } int size(int u){//頂点uが属すグループの大きさを表す. u=find(u); return sz[u]; } std::map<int,std::vector<int>> element(){ std::map<int,std::vector<int>> mp; for(int i=0;i<par.size();i++){ root[i]=find(i); mp[root[i]].push_back(i); } return mp; } }; ll mod_pow(ll x,ll y,ll mod){ ll res=1; while(y>0){ if(y&1){ res*=x; res%=mod; } x*=x; x%=mod; y/=2; } return res; } int main(){ int W,H; cin>>W>>H; UnionFind uf(W+10); string S; for(int q=0;q<H;q++){ cin>>S; map<char,int> mpidx; for(int j=0;j<W;j++){ if('0'<=S[j] && S[j]<='9'){ int num=S[j]-'0'; uf.merge(j,W+num); }else if('a'<=S[j] && S[j]<='z'){ if(!mpidx.count(S[j])){ mpidx[S[j]]=j; }else{ int c=mpidx[S[j]]; uf.merge(c,j); } } } set<int> check; ll ans=1; for(int j=W;j<W+10;j++){ check.insert(uf.find(j)); } if(check.size()!=10){ ans=0; } set<int> st; for(int j=0;j<W+10;j++){ st.insert(uf.find(j)); } int sz=st.size(); ans=ans*mod_pow(10,sz-10,MOD); cout<<ans<<endl; } }