test/aoj/3044.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/3044

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• フィボナッチ探索 (src/Optimization/fibonacci_search.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/3044
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include "src/Optimization/fibonacci_search.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, S, G;
 cin >> N >> M >> S >> G;
 --S, --G;
 int U[M], V[M];
 long long A[M], B[M];
 vector<int> adj[N];
 for (int i= 0; i < M; ++i) {
  cin >> U[i] >> V[i] >> A[i] >> B[i], --U[i], --V[i];
  adj[U[i]].push_back(i), adj[V[i]].push_back(i);
 }
 priority_queue<pair<long long, int>> pq;
 static constexpr long long INF= 1e18;
 long long dist[N];
 fill_n(dist, N, INF);
 dist[S]= 0, pq.emplace(0, S);
 while (!pq.empty()) {
  auto [d, u]= pq.top();
  pq.pop();
  d= -d;
  if (dist[u] != d) continue;
  for (auto e: adj[u]) {
   int v= U[e] ^ V[e] ^ u;
   auto f= [&](long long x) { return x + double(B[e]) / (x + A[e]); };
   auto [_, nd_f]= fibonacci_search<MINIMIZE>(f, d, max(d, B[e]));
   long long nd= ceil(nd_f) + 0.5;
   if (dist[v] > nd) dist[v]= nd, pq.emplace(-nd, v);
  }
 }
 cout << (dist[G] == INF ? -1 : dist[G]) << '\n';
 return 0;
}

#line 1 "test/aoj/3044.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/3044
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#line 2 "src/Optimization/fibonacci_search.hpp"
#include <algorithm>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 6 "src/Optimization/fibonacci_search.hpp"
// [l,r]
template <MinMaxEnum obj, class F> std::pair<int64_t, result_type_t<F>> fibonacci_search(const F &f, int64_t l, int64_t r) {
 assert(l <= r);
 int64_t s= 1, t= 2, a= l - 1, x, b, y;
 for (int64_t e= r - l + 2; t < e;) std::swap(s+= t, t);
 b= a + t, x= b - s;
 result_type_t<F> fx= f(x), fy;
 for (bool g; a + b != 2 * x;) {
  if (y= a + b - x; r < y) b= a, a= y;
  else {
   if constexpr (obj == MINIMIZE) g= fx < (fy= f(y));
   else g= fx > (fy= f(y));
   if (g) b= a, a= y;
   else a= x, x= y, fx= fy;
  }
 }
 return {x, fx};
}
#line 9 "test/aoj/3044.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M, S, G;
 cin >> N >> M >> S >> G;
 --S, --G;
 int U[M], V[M];
 long long A[M], B[M];
 vector<int> adj[N];
 for (int i= 0; i < M; ++i) {
  cin >> U[i] >> V[i] >> A[i] >> B[i], --U[i], --V[i];
  adj[U[i]].push_back(i), adj[V[i]].push_back(i);
 }
 priority_queue<pair<long long, int>> pq;
 static constexpr long long INF= 1e18;
 long long dist[N];
 fill_n(dist, N, INF);
 dist[S]= 0, pq.emplace(0, S);
 while (!pq.empty()) {
  auto [d, u]= pq.top();
  pq.pop();
  d= -d;
  if (dist[u] != d) continue;
  for (auto e: adj[u]) {
   int v= U[e] ^ V[e] ^ u;
   auto f= [&](long long x) { return x + double(B[e]) / (x + A[e]); };
   auto [_, nd_f]= fibonacci_search<MINIMIZE>(f, d, max(d, B[e]));
   long long nd= ceil(nd_f) + 0.5;
   if (dist[v] > nd) dist[v]= nd, pq.emplace(-nd, v);
  }
 }
 cout << (dist[G] == INF ? -1 : dist[G]) << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	6 ms	4 MB
g++-13	00_sample_01.in	AC	5 ms	4 MB
g++-13	00_sample_02.in	AC	5 ms	4 MB
g++-13	00_sample_03.in	AC	5 ms	4 MB
g++-13	00_sample_04.in	AC	5 ms	4 MB
g++-13	02_random_01.in	AC	5 ms	4 MB
g++-13	02_random_02.in	AC	5 ms	4 MB
g++-13	02_random_03.in	AC	5 ms	4 MB
g++-13	02_random_04.in	AC	5 ms	4 MB
g++-13	02_random_05.in	AC	5 ms	4 MB
g++-13	02_random_06.in	AC	5 ms	4 MB
g++-13	02_random_07.in	AC	5 ms	4 MB
g++-13	02_random_08.in	AC	5 ms	4 MB
g++-13	02_random_09.in	AC	5 ms	4 MB
g++-13	02_random_10.in	AC	5 ms	4 MB
g++-13	03_large_01.in	AC	61 ms	16 MB
g++-13	03_large_02.in	AC	56 ms	13 MB
g++-13	03_large_03.in	AC	169 ms	16 MB
g++-13	03_large_04.in	AC	140 ms	16 MB
g++-13	03_large_05.in	AC	156 ms	17 MB
g++-13	12_random_drastic_01.in	AC	6 ms	4 MB
g++-13	12_random_drastic_02.in	AC	5 ms	4 MB
g++-13	12_random_drastic_03.in	AC	5 ms	4 MB
g++-13	12_random_drastic_04.in	AC	5 ms	4 MB
g++-13	12_random_drastic_05.in	AC	5 ms	4 MB
g++-13	12_random_drastic_06.in	AC	5 ms	4 MB
g++-13	12_random_drastic_07.in	AC	5 ms	4 MB
g++-13	12_random_drastic_08.in	AC	5 ms	4 MB
g++-13	12_random_drastic_09.in	AC	5 ms	4 MB
g++-13	12_random_drastic_10.in	AC	5 ms	4 MB
g++-13	13_large_drastic_01.in	AC	142 ms	16 MB
g++-13	13_large_drastic_02.in	AC	54 ms	14 MB
g++-13	13_large_drastic_03.in	AC	168 ms	17 MB
g++-13	13_large_drastic_04.in	AC	138 ms	17 MB
g++-13	13_large_drastic_05.in	AC	115 ms	17 MB
g++-13	24_mukade_large_01.in	AC	229 ms	27 MB
g++-13	24_mukade_large_02.in	AC	270 ms	27 MB
g++-13	24_mukade_large_03.in	AC	284 ms	26 MB
g++-13	24_mukade_large_04.in	AC	258 ms	26 MB
g++-13	24_mukade_large_05.in	AC	186 ms	23 MB
g++-13	25_shell_large_01.in	AC	135 ms	15 MB
g++-13	25_shell_large_02.in	AC	103 ms	12 MB
g++-13	25_shell_large_03.in	AC	95 ms	12 MB
g++-13	25_shell_large_04.in	AC	154 ms	16 MB
g++-13	25_shell_large_05.in	AC	117 ms	13 MB
g++-13	90_corner_01.in	AC	6 ms	4 MB
g++-13	90_corner_02.in	AC	5 ms	4 MB
g++-13	90_corner_03.in	AC	5 ms	4 MB
g++-13	90_corner_04.in	AC	5 ms	4 MB
g++-13	90_corner_05.in	AC	5 ms	4 MB
g++-13	90_corner_06.in	AC	5 ms	4 MB
g++-13	90_corner_07.in	AC	5 ms	4 MB
g++-13	90_corner_08.in	AC	5 ms	4 MB
g++-13	90_corner_09.in	AC	5 ms	4 MB
g++-13	90_corner_10.in	AC	5 ms	4 MB
g++-13	91_corner2_01.in	AC	82 ms	11 MB
g++-13	91_corner2_02.in	AC	65 ms	9 MB
g++-13	91_corner2_03.in	AC	62 ms	8 MB
g++-13	91_corner2_04.in	AC	92 ms	12 MB
g++-13	91_corner2_05.in	AC	100 ms	12 MB
g++-13	99_hand_01.in	AC	6 ms	4 MB
g++-13	99_hand_02.in	AC	5 ms	4 MB
g++-13	99_hand_03.in	AC	5 ms	4 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	00_sample_01.in	AC	5 ms	4 MB
clang++-18	00_sample_02.in	AC	5 ms	4 MB
clang++-18	00_sample_03.in	AC	5 ms	4 MB
clang++-18	00_sample_04.in	AC	5 ms	4 MB
clang++-18	02_random_01.in	AC	5 ms	4 MB
clang++-18	02_random_02.in	AC	5 ms	4 MB
clang++-18	02_random_03.in	AC	5 ms	4 MB
clang++-18	02_random_04.in	AC	5 ms	4 MB
clang++-18	02_random_05.in	AC	5 ms	4 MB
clang++-18	02_random_06.in	AC	5 ms	4 MB
clang++-18	02_random_07.in	AC	5 ms	4 MB
clang++-18	02_random_08.in	AC	5 ms	4 MB
clang++-18	02_random_09.in	AC	5 ms	4 MB
clang++-18	02_random_10.in	AC	5 ms	4 MB
clang++-18	03_large_01.in	AC	61 ms	16 MB
clang++-18	03_large_02.in	AC	58 ms	13 MB
clang++-18	03_large_03.in	AC	176 ms	16 MB
clang++-18	03_large_04.in	AC	176 ms	16 MB
clang++-18	03_large_05.in	AC	166 ms	17 MB
clang++-18	12_random_drastic_01.in	AC	6 ms	4 MB
clang++-18	12_random_drastic_02.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_03.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_04.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_05.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_06.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_07.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_08.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_09.in	AC	5 ms	4 MB
clang++-18	12_random_drastic_10.in	AC	5 ms	4 MB
clang++-18	13_large_drastic_01.in	AC	136 ms	16 MB
clang++-18	13_large_drastic_02.in	AC	52 ms	15 MB
clang++-18	13_large_drastic_03.in	AC	166 ms	17 MB
clang++-18	13_large_drastic_04.in	AC	125 ms	17 MB
clang++-18	13_large_drastic_05.in	AC	113 ms	17 MB
clang++-18	24_mukade_large_01.in	AC	245 ms	27 MB
clang++-18	24_mukade_large_02.in	AC	248 ms	27 MB
clang++-18	24_mukade_large_03.in	AC	237 ms	27 MB
clang++-18	24_mukade_large_04.in	AC	238 ms	26 MB
clang++-18	24_mukade_large_05.in	AC	156 ms	23 MB
clang++-18	25_shell_large_01.in	AC	147 ms	15 MB
clang++-18	25_shell_large_02.in	AC	104 ms	12 MB
clang++-18	25_shell_large_03.in	AC	105 ms	12 MB
clang++-18	25_shell_large_04.in	AC	152 ms	16 MB
clang++-18	25_shell_large_05.in	AC	119 ms	13 MB
clang++-18	90_corner_01.in	AC	6 ms	4 MB
clang++-18	90_corner_02.in	AC	5 ms	4 MB
clang++-18	90_corner_03.in	AC	5 ms	4 MB
clang++-18	90_corner_04.in	AC	5 ms	4 MB
clang++-18	90_corner_05.in	AC	5 ms	4 MB
clang++-18	90_corner_06.in	AC	5 ms	4 MB
clang++-18	90_corner_07.in	AC	5 ms	4 MB
clang++-18	90_corner_08.in	AC	5 ms	4 MB
clang++-18	90_corner_09.in	AC	5 ms	4 MB
clang++-18	90_corner_10.in	AC	5 ms	4 MB
clang++-18	91_corner2_01.in	AC	87 ms	11 MB
clang++-18	91_corner2_02.in	AC	69 ms	9 MB
clang++-18	91_corner2_03.in	AC	66 ms	8 MB
clang++-18	91_corner2_04.in	AC	97 ms	12 MB
clang++-18	91_corner2_05.in	AC	104 ms	12 MB
clang++-18	99_hand_01.in	AC	6 ms	4 MB
clang++-18	99_hand_02.in	AC	5 ms	4 MB
clang++-18	99_hand_03.in	AC	5 ms	4 MB

Back to top page