結果
問題 | No.1451 集団登校 |
ユーザー |
![]() |
提出日時 | 2021-03-31 14:47:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 297 ms / 2,000 ms |
コード長 | 1,070 bytes |
コンパイル時間 | 4,585 ms |
コンパイル使用メモリ | 260,760 KB |
最終ジャッジ日時 | 2025-01-20 01:36:43 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 int main(){ int n,m; cin>>n>>m; dsu D(n); vector<vector<pair<int,mint>>> v(n); rep(i,n)v[i].push_back(make_pair(i,1)); vector<mint> bai(n,1); rep(i,m){ int a,b; cin>>a>>b; a--;b--; if(D.same(a,b))continue; int x = D.leader(a),y = D.leader(b); if(D.size(x)>D.size(y))swap(x,y); if(D.size(x)==D.size(y)){ D.merge(x,y); int z = D.leader(x); bai[z] /= 2; while(v[x^y^z].size()!=0){ v[x^y^z].back().second *= bai[x^y^z]; v[x^y^z].back().second /= 2; v[x^y^z].back().second /= bai[z]; v[z].push_back(v[x^y^z].back()); v[x^y^z].pop_back(); } bai[x^y^z] = 0; } else{ v[x].clear(); D.merge(x,y); } } vector<mint> ans(n,0); rep(i,n){ rep(j,v[i].size()){ ans[v[i][j].first] = v[i][j].second * bai[i]; } } rep(i,n)cout<<ans[i].val()<<endl; return 0; }