結果
問題 |
No.3079 Unite Japanese Prefectures
|
ユーザー |
👑 ![]() |
提出日時 | 2025-03-28 21:52:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 4,000 ms |
コード長 | 2,409 bytes |
コンパイル時間 | 998 ms |
コンパイル使用メモリ | 86,740 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-28 21:52:03 |
合計ジャッジ時間 | 2,588 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<i64(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; namespace nachia { struct DsuFast{ private: std::vector<int> w; public: DsuFast(int n = 0) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int operator[](int u){ return leader(u); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(-w[u] < -w[v]) std::swap(u, v); w[u] += w[v]; w[v] = u; return u; } int size(int u){ return -w[leader(u)]; } bool same(int u, int v){ return leader(u) == leader(v); } }; } // namespace nachia void testcase(){ i64 N, M; cin >> N >> M; auto dsu = nachia::DsuFast(N); vector<vector<pair<i64,i64>>> edges(6); rep(i,M){ i64 u,v,c; cin >> u >> v >> c; u--; v--; c--; edges[c].push_back({u,v}); } vector<i64> cnt(6); rep(d,6){ for(auto [u,v] : edges[d]){ if(dsu.same(u,v)) continue; dsu.merge(u,v); cnt[d] += 1; } } vector<i64> idx(7,1); rep(i,6) idx[i+1] = idx[i] * (cnt[i] + 1); vector<double> dp(idx[6], 0.0); auto Idx = [&](i64 a[6]){ i64 res = 0; rep(i,6) res += idx[i] * a[i]; return res; }; rep(a,cnt[0]+1) rep(b,cnt[1]+1) rep(c,cnt[2]+1) rep(d,cnt[3]+1) rep(e,cnt[4]+1) rep(f,cnt[5]+1){ i64 pos[6] = {a,b,c,d,e,f}; i64 le = -1; i64 ef = 0; double sum = 0.0; rep(d,6){ if(pos[d]) le = d; if(le != -1){ ef += 1; pos[le] -= 1; sum += dp[Idx(pos)]; pos[le] += 1; } } if(ef == 0) continue; sum /= ef; sum += 6.0 / double(ef); dp[Idx(pos)] = sum; } cout.precision(15); cout << fixed; cout << dp[idx[6] - 1] << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }