結果
問題 | No.298 話の伝達 |
ユーザー | chocorusk |
提出日時 | 2019-05-26 10:03:01 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 272 ms / 5,000 ms |
コード長 | 1,883 bytes |
コンパイル時間 | 1,053 ms |
コンパイル使用メモリ | 106,564 KB |
実行使用メモリ | 11,968 KB |
最終ジャッジ日時 | 2023-10-17 17:51:25 |
合計ジャッジ時間 | 3,499 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
11,956 KB |
testcase_01 | AC | 8 ms
11,956 KB |
testcase_02 | AC | 8 ms
11,956 KB |
testcase_03 | AC | 8 ms
11,956 KB |
testcase_04 | AC | 9 ms
11,960 KB |
testcase_05 | AC | 96 ms
11,960 KB |
testcase_06 | AC | 8 ms
11,960 KB |
testcase_07 | AC | 8 ms
11,956 KB |
testcase_08 | AC | 8 ms
11,956 KB |
testcase_09 | AC | 8 ms
11,960 KB |
testcase_10 | AC | 11 ms
11,960 KB |
testcase_11 | AC | 83 ms
11,964 KB |
testcase_12 | AC | 50 ms
11,960 KB |
testcase_13 | AC | 89 ms
11,960 KB |
testcase_14 | AC | 48 ms
11,960 KB |
testcase_15 | AC | 8 ms
11,960 KB |
testcase_16 | AC | 272 ms
11,968 KB |
testcase_17 | AC | 11 ms
11,964 KB |
testcase_18 | AC | 70 ms
11,968 KB |
testcase_19 | AC | 8 ms
11,960 KB |
testcase_20 | AC | 134 ms
11,968 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair<int, int> P; int n, m; bool used[22]; int cmp[22]; vector<P> g[22], gr[22]; vector<int> vs; int ts[22]; void dfs(int x){ used[x]=1; for(auto p:g[x]){ if(!used[p.first]) dfs(p.first); } vs.push_back(x); } void rdfs(int v, int k){ used[v]=1; cmp[v]=k; ts[k]=v; for(auto p:gr[v]){ if(!used[p.first]) rdfs(p.first, k); } } int scc(){ fill(used, used+n, 0); vs.clear(); for(int i=0; i<n; i++){ if(!used[i]) dfs(i); } fill(used, used+n, 0); int k=0; for(int i=vs.size()-1; i>=0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } return k; } int main() { cin>>n>>m; for(int i=0; i<m; i++){ int a, b, c; cin>>a>>b>>c; g[a].push_back({b, c}); gr[b].push_back({a, c}); } scc(); double dp[1<<20]={}; dp[1<<cmp[0]]=1; for(int i=(1<<cmp[0])+1; i<(1<<n); i++){ int j=n-1; while(!(i&(1<<j))) j--; double p=1; for(auto q:gr[ts[j]]){ if(i&(1<<cmp[q.first])) p*=(1.0-(double)q.second/100); } dp[i]=dp[i^(1<<j)]*(1-p); } double ans=0; for(int i=1; i<(1<<n); i++){ if(i&(1<<cmp[n-1])){ for(int j=0; j<n; j++){ if(i&(1<<j)){ for(auto p:g[ts[j]]){ if(!(i&(1<<cmp[p.first]))) dp[i]*=(1.0-(double)p.second/100); } } } ans+=dp[i]; } } printf("%.7lf\n", ans); return 0; }