Submission #8163033
Source Code Expand
Copy
#include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { explicit FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } template< typename T > struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template< typename T > using Edges = vector< edge< T > >; template< typename T > using WeightedGraph = vector< Edges< T > >; using UnWeightedGraph = vector< vector< int > >; template< typename T > using Matrix = vector< vector< T > >; int main() { int N, M; cin >> N >> M; auto dp = make_v< double >(N, N + 1); fill_v(dp, infll); UnWeightedGraph g(N); auto rec = MFP([&](auto rec, int idx) -> void { if(dp[idx][N] < infll) { return; } if(idx + 1 == N) { dp[idx][N] = 0.0; return; } for(auto &to : g[idx]) rec(to); int sz = (int) g[idx].size(); { double ret = 0.0; for(auto &to : g[idx]) ret += dp[to][N]; dp[idx][N] = ret / sz + 1; } { for(int k = idx + 1; k < N; k++) { double ret = 0.0; for(auto &to : g[idx]) ret += min(dp[to][N], dp[to][k]); chmin(dp[idx][k], ret / sz + 1); } } if(sz > 1) { double ret = 0.0; for(auto &to : g[idx]) ret += dp[to][N]; for(auto &to : g[idx]) chmin(dp[idx][idx], (ret - dp[to][N]) / (sz - 1) + 1); } }); for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; --a, --b; g[a].emplace_back(b); } rec(0); cout << *min_element(begin(dp[0]), end(dp[0])) << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Fork in the Road |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 3763 Byte |
Status | AC |
Exec Time | 479 ms |
Memory | 4224 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00-sample-00, 00-sample-01, 00-sample-02 |
All | 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 02-small-10, 02-small-11, 02-small-12, 02-small-13, 02-small-14, 02-small-15, 02-small-16, 02-small-17, 02-small-18, 02-small-19, 02-small-20, 02-small-21, 02-small-22, 02-small-23, 02-small-24, 03-medium-25, 03-medium-26, 03-medium-27, 03-medium-28, 03-medium-29, 03-medium-30, 03-medium-31, 03-medium-32, 03-medium-33, 03-medium-34, 03-medium-35, 03-medium-36, 03-medium-37, 03-medium-38, 03-medium-39, 03-medium-40, 03-medium-41, 03-medium-42, 03-medium-43, 03-medium-44, 04-large-45, 04-large-46, 04-large-47, 04-large-48, 04-large-49, 04-large-50, 04-large-51, 04-large-52, 04-large-53, 04-large-54, 04-large-55, 04-large-56, 04-large-57, 04-large-58, 04-large-59, 04-large-60, 04-large-61, 04-large-62, 04-large-63, 04-large-64 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample-00 | AC | 1 ms | 256 KB |
00-sample-01 | AC | 1 ms | 256 KB |
00-sample-02 | AC | 1 ms | 256 KB |
01-handmade-03 | AC | 479 ms | 4224 KB |
01-handmade-04 | AC | 470 ms | 4224 KB |
01-handmade-05 | AC | 1 ms | 256 KB |
01-handmade-06 | AC | 27 ms | 4224 KB |
01-handmade-07 | AC | 8 ms | 3200 KB |
01-handmade-08 | AC | 38 ms | 3456 KB |
01-handmade-09 | AC | 1 ms | 256 KB |
02-small-10 | AC | 1 ms | 256 KB |
02-small-11 | AC | 1 ms | 256 KB |
02-small-12 | AC | 1 ms | 256 KB |
02-small-13 | AC | 1 ms | 256 KB |
02-small-14 | AC | 1 ms | 256 KB |
02-small-15 | AC | 1 ms | 256 KB |
02-small-16 | AC | 1 ms | 256 KB |
02-small-17 | AC | 1 ms | 256 KB |
02-small-18 | AC | 1 ms | 256 KB |
02-small-19 | AC | 1 ms | 256 KB |
02-small-20 | AC | 1 ms | 256 KB |
02-small-21 | AC | 1 ms | 256 KB |
02-small-22 | AC | 1 ms | 256 KB |
02-small-23 | AC | 1 ms | 256 KB |
02-small-24 | AC | 1 ms | 256 KB |
03-medium-25 | AC | 1 ms | 256 KB |
03-medium-26 | AC | 1 ms | 384 KB |
03-medium-27 | AC | 1 ms | 256 KB |
03-medium-28 | AC | 1 ms | 256 KB |
03-medium-29 | AC | 2 ms | 384 KB |
03-medium-30 | AC | 1 ms | 256 KB |
03-medium-31 | AC | 1 ms | 256 KB |
03-medium-32 | AC | 1 ms | 256 KB |
03-medium-33 | AC | 2 ms | 384 KB |
03-medium-34 | AC | 2 ms | 384 KB |
03-medium-35 | AC | 1 ms | 384 KB |
03-medium-36 | AC | 1 ms | 256 KB |
03-medium-37 | AC | 2 ms | 384 KB |
03-medium-38 | AC | 1 ms | 256 KB |
03-medium-39 | AC | 1 ms | 256 KB |
03-medium-40 | AC | 1 ms | 384 KB |
03-medium-41 | AC | 1 ms | 256 KB |
03-medium-42 | AC | 2 ms | 384 KB |
03-medium-43 | AC | 2 ms | 384 KB |
03-medium-44 | AC | 2 ms | 384 KB |
04-large-45 | AC | 3 ms | 2816 KB |
04-large-46 | AC | 5 ms | 3072 KB |
04-large-47 | AC | 18 ms | 2944 KB |
04-large-48 | AC | 31 ms | 3072 KB |
04-large-49 | AC | 84 ms | 3200 KB |
04-large-50 | AC | 3 ms | 2944 KB |
04-large-51 | AC | 4 ms | 2944 KB |
04-large-52 | AC | 18 ms | 3072 KB |
04-large-53 | AC | 39 ms | 3328 KB |
04-large-54 | AC | 154 ms | 3584 KB |
04-large-55 | AC | 3 ms | 2688 KB |
04-large-56 | AC | 5 ms | 3200 KB |
04-large-57 | AC | 18 ms | 2944 KB |
04-large-58 | AC | 33 ms | 3200 KB |
04-large-59 | AC | 77 ms | 3200 KB |
04-large-60 | AC | 3 ms | 3072 KB |
04-large-61 | AC | 5 ms | 3200 KB |
04-large-62 | AC | 17 ms | 3328 KB |
04-large-63 | AC | 40 ms | 3456 KB |
04-large-64 | AC | 156 ms | 3712 KB |