結果
問題 |
No.2160 みたりのDominator
|
ユーザー |
![]() |
提出日時 | 2022-12-08 13:23:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 622 ms / 2,000 ms |
コード長 | 2,645 bytes |
コンパイル時間 | 2,948 ms |
コンパイル使用メモリ | 233,464 KB |
最終ジャッジ日時 | 2025-02-09 06:23:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 93 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/scc> #include<atcoder/dsu> using namespace std; using namespace atcoder; #define rep(i,n) for(int i=0;i<int(n);++i) using lint=long long; int main(){ array<int,3>n; int m,ns=0; rep(i,3)cin>>n[i]; rep(i,3)ns+=n[i]; cin>>m; vector<int>u(m),v(m),st; rep(i,m){ cin>>u[i]>>v[i]; u[i]--;v[i]--; st.emplace_back(u[i]); st.emplace_back(v[i]); } st.emplace_back(ns); st.emplace_back(ns+1); sort(st.begin(),st.end()); st.erase(unique(st.begin(),st.end()),st.end()); int n2=st.size(); vector<vector<pair<int,int>>> g(n2); scc_graph scc(n2); auto get=[&](int i){ return lower_bound(st.begin(),st.end(),i)-st.begin(); }; //cerr<<n2<<endl; { int now=0,pre=0; rep(i,3){ //cerr<<st[now]<<endl; if(st[now]>=pre+n[i]){ g[n2-2].emplace_back(n2-1,n[i]+1); pre+=n[i]; continue; } g[n2-2].emplace_back(now,st[now]-pre+1); while(1){ if(st[now+1]-pre>=n[i])break; g[now].emplace_back(now+1,(st[now+1]-pre+1)-(st[now]-pre+1)); now++; } g[now].emplace_back(n2-1,(n[i]+1)-(st[now]-pre+1)); now++; pre+=n[i]; } } rep(i,m){ g[get(u[i])].emplace_back(get(v[i]),1); g[get(v[i])].emplace_back(get(u[i]),1); } rep(i,n2){ for(auto [e,c]:g[i]){ scc.add_edge(i,e); } } auto res=scc.scc(); int sz=res.size(); vector<vector<pair<lint,lint>>>g2(sz); vector<int>id(n2); rep(i,sz){ for(auto s:res[i]){ id[s]=i; } } rep(j,sz){ map<lint,lint>l; for(auto i:res[j]){ for(auto [e,c]:g[i]){ if(id[i]==id[e])continue; if(l[id[e]]==0)l[id[e]]=1; l[id[e]]*=c; } } for(auto [e,c]:l){ g2[j].emplace_back(e,c); } } lint ans=0,tmp=1; vector<lint>div(sz,1),deg(sz); rep(i,sz){ for(auto [e,c]:g2[i]){ deg[e]++; } } rep(i,sz-1){ if(deg[i]==1&&g2[i].size()==1)continue; tmp/=div[i]; for(auto [e,c]:g2[i]){ lint to=e; while(deg[to]==1&&g2[to].size()==1){ c+=g2[to][0].second; to=g2[to][0].first; } tmp*=c; div[to]*=c; } //cerr<<tmp<<endl; ans+=tmp; } cout<<ans<<endl; /**/}