Submission #8162737


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][0] < 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 0
Code Size 3763 Byte
Status
Exec Time 2103 ms
Memory 6272 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00-sample-00, 00-sample-01, 00-sample-02
All 0 / 600 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 1 ms 256 KB
00-sample-01 1 ms 256 KB
00-sample-02 1 ms 256 KB
01-handmade-03 2103 ms 6272 KB
01-handmade-04 2103 ms 4224 KB
01-handmade-05 1 ms 256 KB
01-handmade-06 28 ms 4224 KB
01-handmade-07 8 ms 3200 KB
01-handmade-08 2103 ms 3456 KB
01-handmade-09 1 ms 256 KB
02-small-10 1 ms 256 KB
02-small-11 1 ms 256 KB
02-small-12 1 ms 256 KB
02-small-13 1 ms 256 KB
02-small-14 1 ms 256 KB
02-small-15 1 ms 256 KB
02-small-16 1 ms 256 KB
02-small-17 1 ms 256 KB
02-small-18 1 ms 256 KB
02-small-19 1 ms 256 KB
02-small-20 1 ms 256 KB
02-small-21 1 ms 256 KB
02-small-22 1 ms 256 KB
02-small-23 1 ms 256 KB
02-small-24 1 ms 256 KB
03-medium-25 1 ms 256 KB
03-medium-26 646 ms 384 KB
03-medium-27 2103 ms 256 KB
03-medium-28 2103 ms 256 KB
03-medium-29 2103 ms 384 KB
03-medium-30 1 ms 256 KB
03-medium-31 427 ms 256 KB
03-medium-32 2103 ms 256 KB
03-medium-33 2103 ms 384 KB
03-medium-34 2103 ms 384 KB
03-medium-35 1 ms 384 KB
03-medium-36 1713 ms 256 KB
03-medium-37 2103 ms 384 KB
03-medium-38 2103 ms 256 KB
03-medium-39 243 ms 256 KB
03-medium-40 1 ms 384 KB
03-medium-41 459 ms 256 KB
03-medium-42 2103 ms 384 KB
03-medium-43 2103 ms 384 KB
03-medium-44 2103 ms 384 KB
04-large-45 5 ms 2816 KB
04-large-46 2103 ms 3072 KB
04-large-47 2103 ms 2944 KB
04-large-48 2103 ms 5120 KB
04-large-49 2103 ms 3200 KB
04-large-50 3 ms 2944 KB
04-large-51 2103 ms 2944 KB
04-large-52 2103 ms 3072 KB
04-large-53 2103 ms 3328 KB
04-large-54 2103 ms 3584 KB
04-large-55 5 ms 2688 KB
04-large-56 2103 ms 3200 KB
04-large-57 2103 ms 2944 KB
04-large-58 2103 ms 3200 KB
04-large-59 2103 ms 5248 KB
04-large-60 4 ms 3072 KB
04-large-61 2103 ms 3200 KB
04-large-62 2103 ms 3328 KB
04-large-63 2103 ms 3456 KB
04-large-64 2103 ms 3712 KB