結果
問題 | No.1290 Addition and Subtraction Operation |
ユーザー |
![]() |
提出日時 | 2020-11-13 22:47:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 25,555 bytes |
コンパイル時間 | 3,046 ms |
コンパイル使用メモリ | 263,764 KB |
最終ジャッジ日時 | 2025-01-15 23:44:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 85 |
ソースコード
#line 1 "other/b.cc"/* @file template.cpp* @brief Template*/#include <bits/extc++.h>#line 2 "Library/alias.hpp"/** @file alias.hpp* @brief Alias*/#line 13 "Library/alias.hpp"namespace workspace {constexpr char eol = '\n';using namespace std;using i32 = int_least32_t;using i64 = int_least64_t;using i128 = __int128_t;using u32 = uint_least32_t;using u64 = uint_least64_t;using u128 = __uint128_t;template <class T, class Comp = less<T>>using priority_queue = std::priority_queue<T, vector<T>, Comp>;template <class T> using stack = std::stack<T, vector<T>>;} // namespace workspace#line 2 "Library/config.hpp"/** @file config.hpp* @brief Configuration*/#line 11 "Library/config.hpp"namespace config {const auto start_time{std::chrono::system_clock::now()};/** @fn elapsed* @return elapsed time of the program*/int64_t elapsed() {using namespace std::chrono;const auto end_time{system_clock::now()};return duration_cast<milliseconds>(end_time - start_time).count();}/** @fn setup* @brief setup I/O before main process.*/__attribute__((constructor)) void setup() {using namespace std;ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);#ifdef _buffer_checkatexit([] {char bufc;if (cin >> bufc)cerr << "\n\033[43m\033[30mwarning: buffer not empty.\033[0m\n\n";});#endif}unsigned cases(), caseid = 1; // current case number, 1-indexed/** @fn loop* @brief iterate cases.* @param main called once per case*/template <class F> void loop(F main) {for (const unsigned total = cases(); caseid <= total; ++caseid) {try {main();} catch (std::nullptr_t) {}}}} // namespace config#line 2 "Library/cxx20.hpp"/** @file cxx20.hpp* @brief C++20 Features*/#if __cplusplus <= 201703L#if __has_include(<bit>)#include <bit>#endif#include <vector>namespace std {/** @fn erase_if* @brief Erase the elements of a container that do not satisfy the condition.* @param __cont Container.* @param __pred Predicate.* @return Number of the erased elements.*/template <typename _Tp, typename _Alloc, typename _Predicate>inline typename vector<_Tp, _Alloc>::size_type erase_if(vector<_Tp, _Alloc>& __cont, _Predicate __pred) {const auto __osz = __cont.size();__cont.erase(std::remove_if(__cont.begin(), __cont.end(), __pred),__cont.end());return __osz - __cont.size();}/** @fn erase* @brief Erase the elements of a container that are equal to the given value.* @param __cont Container.* @param __value Value.* @return Number of the erased elements.*/template <typename _Tp, typename _Alloc, typename _Up>inline typename vector<_Tp, _Alloc>::size_type erase(vector<_Tp, _Alloc>& __cont, const _Up& __value) {const auto __osz = __cont.size();__cont.erase(std::remove(__cont.begin(), __cont.end(), __value),__cont.end());return __osz - __cont.size();}} // namespace std#endif#line 2 "Library/option.hpp"/** @file option.hpp* @brief Optimize Options*/#ifdef ONLINE_JUDGE#pragma GCC optimize("O3")#pragma GCC target("avx,avx2")#pragma GCC optimize("unroll-loops")#endif#line 2 "Library/utils.hpp"/** @file utils.hpp* @brief All headers in utlis*/#line 2 "Library/utils/binary_search.hpp"/** @file binary_search.hpp* @brief Binary Search*/#if __cplusplus >= 201703L#include <cassert>#include <cmath>#include <vector>namespace workspace {/** @fn binary_search* @brief binary search on a discrete range.* @param ok pred(ok) is true* @param ng pred(ng) is false* @param pred the predicate* @return the closest point to (ng) where pred is true*/template <class iter_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, iter_type>, bool>,iter_type>binary_search(iter_type ok, iter_type ng, pred_type pred) {assert(ok != ng);std::make_signed_t<decltype(ng - ok)> dist(ng - ok);while (1 < dist || dist < -1) {iter_type mid(ok + dist / 2);if (pred(mid))ok = mid, dist -= dist / 2;elseng = mid, dist /= 2;}return ok;}/** @fn parallel_binary_search* @brief parallel binary search on discrete ranges.* @param ends a vector of pairs; pred(first) is true, pred(second) is false* @param pred the predicate* @return the closest points to (second) where pred is true*/template <class iter_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, std::vector<iter_type>>,std::vector<bool>>,std::vector<iter_type>>parallel_binary_search(std::vector<std::pair<iter_type, iter_type>> ends,pred_type pred) {std::vector<iter_type> mids(ends.size());for (;;) {bool all_found = true;for (size_t i{}; i != ends.size(); ++i) {auto [ok, ng] = ends[i];iter_type mid(ok + (ng - ok) / 2);if (mids[i] != mid) {all_found = false;mids[i] = mid;}}if (all_found) break;auto res = pred(mids);for (size_t i{}; i != ends.size(); ++i) {(res[i] ? ends[i].first : ends[i].second) = mids[i];}}return mids;}/** @fn binary_search* @brief binary search on the real number line.* @param ok pred(ok) is true* @param ng pred(ng) is false* @param eps the error tolerance* @param pred the predicate* @return the boundary point*/template <class real_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, real_type>, bool>,real_type>binary_search(real_type ok, real_type ng, const real_type eps, pred_type pred) {assert(ok != ng);for (auto loops = 0; loops != std::numeric_limits<real_type>::digits &&(ok + eps < ng || ng + eps < ok);++loops) {real_type mid{(ok + ng) / 2};(pred(mid) ? ok : ng) = mid;}return ok;}/** @fn parallel_binary_search* @brief parallel binary search on the real number line.* @param ends a vector of pairs; pred(first) is true, pred(second) is false* @param eps the error tolerance* @param pred the predicate* @return the boundary points*/template <class real_type, class pred_type>std::enable_if_t<std::is_convertible_v<std::invoke_result_t<pred_type, std::vector<real_type>>,std::vector<bool>>,std::vector<real_type>>parallel_binary_search(std::vector<std::pair<real_type, real_type>> ends,const real_type eps, pred_type pred) {std::vector<real_type> mids(ends.size());for (auto loops = 0; loops != std::numeric_limits<real_type>::digits;++loops) {bool all_found = true;for (size_t i{}; i != ends.size(); ++i) {auto [ok, ng] = ends[i];if (ok + eps < ng || ng + eps < ok) {all_found = false;mids[i] = (ok + ng) / 2;}}if (all_found) break;auto res = pred(mids);for (size_t i{}; i != ends.size(); ++i) {(res[i] ? ends[i].first : ends[i].second) = mids[i];}}return mids;}} // namespace workspace#endif#line 2 "Library/utils/casefmt.hpp"/** @file castfmt* @brief Case Output Format*/#line 9 "Library/utils/casefmt.hpp"namespace workspace {/** @brief printf("Case #%u: ", config::caseid)* @param os reference to ostream* @return os*/std::ostream& casefmt(std::ostream& os) {return os << "Case #" << config::caseid << ": ";}} // namespace workspace#line 2 "Library/utils/chval.hpp"/** @file chval.hpp* @brief Change Less/Greater*/#line 9 "Library/utils/chval.hpp"namespace workspace {/** @fn chle* @brief Substitute y for x if comp(y, x) is true.* @param x Reference* @param y Const reference* @param comp Compare function* @return Whether or not x is updated*/template <class Tp, class Comp = std::less<Tp>>bool chle(Tp &x, const Tp &y, Comp comp = Comp()) {return comp(y, x) ? x = y, true : false;}/** @fn chge* @brief Substitute y for x if comp(x, y) is true.* @param x Reference* @param y Const reference* @param comp Compare function* @return Whether or not x is updated*/template <class Tp, class Comp = std::less<Tp>>bool chge(Tp &x, const Tp &y, Comp comp = Comp()) {return comp(x, y) ? x = y, true : false;}} // namespace workspace#line 5 "Library/utils/coordinate_compression.hpp"template <class T> class coordinate_compression {std::vector<T> uniquely;std::vector<size_t> compressed;public:coordinate_compression(const std::vector<T> &raw): uniquely(raw), compressed(raw.size()) {std::sort(uniquely.begin(), uniquely.end());uniquely.erase(std::unique(uniquely.begin(), uniquely.end()),uniquely.end());for (size_t i = 0; i != size(); ++i)compressed[i] =std::lower_bound(uniquely.begin(), uniquely.end(), raw[i]) -uniquely.begin();}size_t operator[](const size_t idx) const {assert(idx < size());return compressed[idx];}size_t size() const { return compressed.size(); }size_t count() const { return uniquely.size(); }T value(const size_t ord) const {assert(ord < count());return uniquely[ord];}size_t order(const T &value) const {return std::lower_bound(uniquely.begin(), uniquely.end(), value) -uniquely.begin();}auto begin() { return compressed.begin(); }auto end() { return compressed.end(); }auto rbegin() { return compressed.rbegin(); }auto rend() { return compressed.rend(); }};#line 2 "Library/utils/ejection.hpp"/** @file ejection.hpp* @brief Ejection*/#line 9 "Library/utils/ejection.hpp"namespace workspace {/** @brief eject from a try block, throw nullptr* @param arg output*/template <class Tp> void eject(Tp const &arg) {std::cout << arg << "\n";throw nullptr;}} // namespace workspace#line 2 "Library/utils/fixed_point.hpp"/** @file fixed_point.hpp* @brief Fixed Point Combinator*/#line 9 "Library/utils/fixed_point.hpp"namespace workspace {/** @class fixed_point* @brief Recursive calling of lambda expression.*/template <class lambda_type> class fixed_point {lambda_type func;public:/** @param func 1st arg callable with the rest of args, and the return type* specified.*/fixed_point(lambda_type &&func) : func(std::move(func)) {}/** @brief Recursively apply *this to 1st arg of func.* @param args Arguments of the recursive method.*/template <class... Args> auto operator()(Args &&... args) const {return func(*this, std::forward<Args>(args)...);}};} // namespace workspace#line 6 "Library/utils/hash.hpp"#line 2 "Library/utils/sfinae.hpp"/** @file sfinae.hpp* @brief SFINAE syntax*/#line 10 "Library/utils/sfinae.hpp"#include <type_traits>template <class type, template <class> class trait>using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type;template <class Container>using element_type = typename std::decay<decltype(*std::begin(std::declval<Container&>()))>::type;template <class T, class = int> struct mapped_of {using type = element_type<T>;};template <class T>struct mapped_of<T,typename std::pair<int, typename T::mapped_type>::first_type> {using type = typename T::mapped_type;};template <class T> using mapped_type = typename mapped_of<T>::type;template <class T, class = void> struct is_integral_ext : std::false_type {};template <class T>struct is_integral_ext<T, typename std::enable_if<std::is_integral<T>::value>::type>: std::true_type {};template <> struct is_integral_ext<__int128_t> : std::true_type {};template <> struct is_integral_ext<__uint128_t> : std::true_type {};#if __cplusplus >= 201402template <class T>constexpr static bool is_integral_ext_v = is_integral_ext<T>::value;#endiftemplate <typename T, typename = void> struct multiplicable_uint {using type = uint_least32_t;};template <typename T>struct multiplicable_uint<T, typename std::enable_if<(2 < sizeof(T))>::type> {using type = uint_least64_t;};template <typename T>struct multiplicable_uint<T, typename std::enable_if<(4 < sizeof(T))>::type> {using type = __uint128_t;};#line 8 "Library/utils/hash.hpp"namespace workspace {template <class T, class = void> struct hash : std::hash<T> {};#if __cplusplus >= 201703Ltemplate <class Unique_bits_type>struct hash<Unique_bits_type,enable_if_trait_type<Unique_bits_type,std::has_unique_object_representations>> {size_t operator()(uint64_t x) const {static const uint64_t m = std::random_device{}();x ^= x >> 23;x ^= m;x ^= x >> 47;return x - (x >> 32);}};#endiftemplate <class Key> size_t hash_combine(const size_t &seed, const Key &key) {return seed ^(hash<Key>()(key) + 0x9e3779b9 /* + (seed << 6) + (seed >> 2) */);}template <class T1, class T2> struct hash<std::pair<T1, T2>> {size_t operator()(const std::pair<T1, T2> &pair) const {return hash_combine(hash<T1>()(pair.first), pair.second);}};template <class... T> class hash<std::tuple<T...>> {template <class Tuple, size_t index = std::tuple_size<Tuple>::value - 1>struct tuple_hash {static uint64_t apply(const Tuple &t) {return hash_combine(tuple_hash<Tuple, index - 1>::apply(t),std::get<index>(t));}};template <class Tuple> struct tuple_hash<Tuple, size_t(-1)> {static uint64_t apply(const Tuple &t) { return 0; }};public:uint64_t operator()(const std::tuple<T...> &t) const {return tuple_hash<std::tuple<T...>>::apply(t);}};template <class hash_table> struct hash_table_wrapper : hash_table {using key_type = typename hash_table::key_type;size_t count(const key_type &key) const {return hash_table::find(key) != hash_table::end();}template <class... Args> auto emplace(Args &&... args) {return hash_table::insert(typename hash_table::value_type(args...));}};template <class Key, class Mapped = __gnu_pbds::null_type>using cc_hash_table =hash_table_wrapper<__gnu_pbds::cc_hash_table<Key, Mapped, hash<Key>>>;template <class Key, class Mapped = __gnu_pbds::null_type>using gp_hash_table =hash_table_wrapper<__gnu_pbds::gp_hash_table<Key, Mapped, hash<Key>>>;template <class Key, class Mapped>using unordered_map = std::unordered_map<Key, Mapped, hash<Key>>;template <class Key> using unordered_set = std::unordered_set<Key, hash<Key>>;} // namespace workspace#line 2 "Library/utils/make_vector.hpp"/** @file make_vector.hpp* @brief Multi-dimensional Vector*/#if __cplusplus >= 201703L#include <tuple>#include <vector>namespace workspace {/** @brief Make a multi-dimensional vector.* @tparam Tp type of the elements* @tparam N dimension* @tparam S integer type* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N, typename S>constexpr auto make_vector(S* sizes, Tp const& init = Tp()) {static_assert(std::is_convertible_v<S, size_t>);if constexpr (N)return std::vector(*sizes,make_vector<Tp, N - 1, S>(std::next(sizes), init));elsereturn init;}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N, typename S>constexpr auto make_vector(const S (&sizes)[N], Tp const& init = Tp()) {return make_vector<Tp, N, S>((S*)sizes, init);}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N, typename S, size_t I = 0>constexpr auto make_vector(std::array<S, N> const& sizes,Tp const& init = Tp()) {static_assert(std::is_convertible_v<S, size_t>);if constexpr (I == N)return init;elsereturn std::vector(sizes[I], make_vector<Tp, N, S, I + 1>(sizes, init));}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, size_t N = SIZE_MAX, size_t I = 0, class... Args>constexpr auto make_vector(std::tuple<Args...> const& sizes,Tp const& init = Tp()) {using tuple_type = std::tuple<Args...>;if constexpr (I == std::tuple_size_v<tuple_type> || I == N)return init;else {static_assert(std::is_convertible_v<std::tuple_element_t<I, tuple_type>, size_t>);return std::vector(std::get<I>(sizes),make_vector<Tp, N, I + 1>(sizes, init));}}/** @brief Make a multi-dimensional vector.* @param sizes The size of each dimension* @param init The initial value*/template <typename Tp, class Fst, class Snd>constexpr auto make_vector(std::pair<Fst, Snd> const& sizes,Tp const& init = Tp()) {static_assert(std::is_convertible_v<Fst, size_t>);static_assert(std::is_convertible_v<Snd, size_t>);return make_vector({(size_t)sizes.first, (size_t)sizes.second}, init);}} // namespace workspace#endif#line 3 "Library/utils/random_number_generator.hpp"template <typename num_type> class random_number_generator {typename std::conditional<std::is_integral<num_type>::value,std::uniform_int_distribution<num_type>,std::uniform_real_distribution<num_type>>::typeunif;std::mt19937 engine;public:random_number_generator(num_type min = std::numeric_limits<num_type>::min(),num_type max = std::numeric_limits<num_type>::max()): unif(min, max), engine(std::random_device{}()) {}num_type min() const { return unif.min(); }num_type max() const { return unif.max(); }// generate a random number in [min(), max()].num_type operator()() { return unif(engine); }};#line 3 "Library/utils/read.hpp"namespace workspace {// read with std::cin.template <class T = void>struct read{typename std::remove_const<T>::type value;template <class... types>read(types... args) : value(args...) { std::cin >> value; }operator T() const { return value; }};template <>struct read<void>{template <class T>operator T() const { T value; std::cin >> value; return value; }};} // namespace workspace#line 2 "Library/utils/round_div.hpp"/** @file round_div.hpp* @brief Round Integer Division*/#line 9 "Library/utils/round_div.hpp"#line 11 "Library/utils/round_div.hpp"namespace workspace {/** @fn floor_div* @brief floor of fraction.* @param x the numerator* @param y the denominator* @return maximum integer z s.t. z <= x / y* @note y must be nonzero.*/template <typename T1, typename T2>constexpr typename std::enable_if<(is_integral_ext<T1>::value &&is_integral_ext<T2>::value),typename std::common_type<T1, T2>::type>::typefloor_div(T1 x, T2 y) {assert(y != 0);if (y < 0) x = -x, y = -y;return x < 0 ? (x - y + 1) / y : x / y;}/** @fn ceil_div* @brief ceil of fraction.* @param x the numerator* @param y the denominator* @return minimum integer z s.t. z >= x / y* @note y must be nonzero.*/template <typename T1, typename T2>constexpr typename std::enable_if<(is_integral_ext<T1>::value &&is_integral_ext<T2>::value),typename std::common_type<T1, T2>::type>::typeceil_div(T1 x, T2 y) {assert(y != 0);if (y < 0) x = -x, y = -y;return x < 0 ? x / y : (x + y - 1) / y;}} // namespace workspace#line 4 "Library/utils/stream.hpp"#line 6 "Library/utils/stream.hpp"namespace std {template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {return is >> p.first >> p.second;}template <class T, class U>ostream &operator<<(ostream &os, const pair<T, U> &p) {return os << p.first << ' ' << p.second;}template <class tuple_t, size_t index> struct tuple_is {static istream &apply(istream &is, tuple_t &t) {tuple_is<tuple_t, index - 1>::apply(is, t);return is >> get<index>(t);}};template <class tuple_t> struct tuple_is<tuple_t, SIZE_MAX> {static istream &apply(istream &is, tuple_t &t) { return is; }};template <class... T> istream &operator>>(istream &is, tuple<T...> &t) {return tuple_is<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(is,t);}template <class tuple_t, size_t index> struct tuple_os {static ostream &apply(ostream &os, const tuple_t &t) {tuple_os<tuple_t, index - 1>::apply(os, t);return os << ' ' << get<index>(t);}};template <class tuple_t> struct tuple_os<tuple_t, 0> {static ostream &apply(ostream &os, const tuple_t &t) {return os << get<0>(t);}};template <class tuple_t> struct tuple_os<tuple_t, SIZE_MAX> {static ostream &apply(ostream &os, const tuple_t &t) { return os; }};template <class... T> ostream &operator<<(ostream &os, const tuple<T...> &t) {return tuple_os<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply(os,t);}template <class Container, typename Value = element_type<Container>>typename enable_if<!is_same<typename decay<Container>::type, string>::value &&!is_same<typename decay<Container>::type, char *>::value,istream &>::typeoperator>>(istream &is, Container &cont) {for (auto &&e : cont) is >> e;return is;}template <class Container, typename Value = element_type<Container>>typename enable_if<!is_same<typename decay<Container>::type, string>::value &&!is_same<typename decay<Container>::type, char *>::value,ostream &>::typeoperator<<(ostream &os, const Container &cont) {bool head = true;for (auto &&e : cont) head ? head = 0 : (os << ' ', 0), os << e;return os;}} // namespace std#line 4 "Library/utils/trinary_search.hpp"// trinary search on discrete range.template <class iter_type, class comp_type>iter_type trinary(iter_type first, iter_type last, comp_type comp){assert(first < last);intmax_t dist(last - first);while(dist > 2){iter_type left(first + dist / 3), right(first + dist * 2 / 3);if(comp(left, right)) last = right, dist = dist * 2 / 3;else first = left, dist -= dist / 3;}if(dist > 1 && comp(first + 1, first)) ++first;return first;}// trinary search on real numbers.template <class comp_type>long double trinary(long double first, long double last, const long double eps, comp_type comp){assert(first < last);while(last - first > eps){long double left{(first * 2 + last) / 3}, right{(first + last * 2) / 3};if(comp(left, right)) last = right;else first = left;}return first;}#line 2 "Library/utils/wrapper.hpp"template <class Container> class reversed {Container &ref, copy;public:constexpr reversed(Container &ref) : ref(ref) {}constexpr reversed(Container &&ref = Container()) : ref(copy), copy(ref) {}constexpr auto begin() const { return ref.rbegin(); }constexpr auto end() const { return ref.rend(); }constexpr operator Container() const { return ref; }};#line 12 "other/b.cc"namespace workspace {void main();}int main() { config::loop(workspace::main); }unsigned config::cases() {// return -1; // unspecified// int t; std::cin >> t; std::cin.ignore(); return t; // givenreturn 1;}#line 4 "Library/data_structure/union_find/basic.hpp"struct union_find{union_find(const size_t &n = 0) : link(n, -1) {}size_t find(const size_t &x){assert(x < size());return link[x] < 0 ? x : (link[x] = find(link[x]));}size_t size() const { return link.size(); }size_t size(const size_t &x){assert(x < size());return -link[find(x)];}bool same(const size_t &x, const size_t &y){assert(x < size() && y < size());return find(x) == find(y);}virtual bool unite(size_t x, size_t y){assert(x < size() && y < size());x = find(x), y = find(y);if(x == y) return false;if(link[x] > link[y]) std::swap(x, y);link[x] += link[y];link[y] = x;return true;}protected:std::vector<int> link;}; // class union_find#line 25 "other/b.cc"namespace workspace {void main() {// start here!int n, m;cin >> n >> m;vector<int> b(n);cin >> b;for (auto i = 0; i < n; ++i) {if (i & 1) b[i] = -b[i];}b.emplace_back(0);for (auto i = n; i > 0; --i) {b[i] -= b[i - 1];}union_find uf(n + 1);for (auto i = 0; i < m; ++i) {int u, v;cin >> u >> v;--u;uf.unite(u, v);}vector<i64> sum(n);for (auto i = 0; i <= n; ++i) {sum[uf.find(i)] += b[i];}cout << (none_of(begin(sum), end(sum), [](auto v) { return v != 0; }) ? "YES": "NO")<< eol;}} // namespace workspace