Submission #22314233


Source Code Expand

Copy
#include <utility>
#include <bits/stdc++.h>
#include <cmath>
#include <random>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
constexpr i32 operator"" _i32(u64 v) { return v; }
constexpr u32 operator"" _u32(u64 v) { return v; }
constexpr i64 operator"" _i64(u64 v) { return v; }
constexpr u64 operator"" _u64(u64 v) { return v; }
using f64 = double;
using f80 = long double;
using f128 = __float128;
constexpr f64 operator"" _f64(f80 v) { return v; }
constexpr f80 operator"" _f80(f80 v) { return v; }
template<int n> using BSet = std::bitset<n>;
template<typename T1, typename T2> using Pair = std::pair<T1, T2>;
template<typename... Ts> using Tup = std::tuple<Ts...>;
template<typename T, int N> using Arr = std::array<T, N>;
template<typename... Ts> using Deq = std::deque<Ts...>;
template<typename... Ts> using Set = std::set<Ts...>;
template<typename... Ts> using MSet = std::multiset<Ts...>;
template<typename... Ts> using USet = std::unordered_set<Ts...>;
template<typename... Ts> using UMSet = std::unordered_multiset<Ts...>;
template<typename... Ts> using Map = std::map<Ts...>;
template<typename... Ts> using MMap = std::multimap<Ts...>;
template<typename... Ts> using UMap = std::unordered_map<Ts...>;
template<typename... Ts> using UMMap = std::unordered_multimap<Ts...>;
template<typename... Ts> using Vec = std::vector<Ts...>;
template<typename... Ts> using Stack = std::stack<Ts...>;
template<typename... Ts> using Queue = std::queue<Ts...>;
template<typename T> using MaxHeap = std::priority_queue<T>;
template<typename T> using MinHeap = std::priority_queue<T, Vec<T>, std::greater<T>>;
template<typename T> constexpr T INF = std::numeric_limits<T>::max() / 4;
template<typename T> constexpr T PI = T{3.141592653589793238462643383279502884};
template<typename T> constexpr T TEN(const int n) { return n == 0 ? T{1} : TEN<T>(n - 1) * T{10}; }
constexpr int popcount(const u64 v) { return v ? __builtin_popcountll(v) : 0; }
constexpr int log2p1(const u64 v) { return v ? 64 - __builtin_clzll(v) : 0; }
constexpr int lsbp1(const u64 v) { return __builtin_ffsll(v); }
constexpr int clog(const u64 v) { return v ? log2p1(v - 1) : 0; }
constexpr u64 ceil2(const u64 v) { return 1_u64 << clog(v); }
constexpr u64 floor2(const u64 v) { return v ? (1_u64 << (log2p1(v) - 1)) : 0_u64; }
constexpr bool ispow2(const u64 v) { return (v & (v - 1)) == 0; }
constexpr bool btest(const u64 mask, const int ind) { return (mask >> ind) & 1_u64; }
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }
template<typename F> struct Fixpoint : F
{
    Fixpoint(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T, typename F>
Vec<T> genVec(int n, F f)
{
    Vec<T> ans;
    return std::generate_n(std::back_insert_iterator(ans), n, f), ans;
}
template<typename T>
Vec<T> iota(int n, T offset = T{})
{
    Vec<T> ans(n);
    return std::iota(ans.begin(), ans.end(), offset), ans;
}
template<typename T, typename F = std::less<T>>
Vec<T> iota(const Vec<T>& vs, F comp = F{})
{
    auto is = iota((int)vs.size(), 0);
    return std::sort(is.begin(), is.end(), [&](int i, int j) { return comp(vs[i], vs[j]); }), is;
}
template<typename T, int n, int i = 0>
auto ndVec(int const (&szs)[n], const T x = T{})
{
    if constexpr (i == n) {
        return x;
    } else {
        return std::vector(szs[i], ndVec<T, n, i + 1>(szs, x));
    }
}
template<typename T>
T fdiv(T x, T y)
{
    if (y < T{}) { x = -x, y = -y; }
    return x >= T{} ? x / y : (x - y + 1) / y;
}
template<typename T>
T cdiv(T x, T y)
{
    if (y < T{}) { x = -x, y = -y; }
    return x >= T{} ? (x + y - 1) / y : x / y;
}
class range
{
private:
    struct itr
    {
        itr(const int start = 0, const int step = 1) : m_cnt{start}, m_step{step} {}
        bool operator!=(const itr& it) const { return m_cnt != it.m_cnt; }
        int& operator*() { return m_cnt; }
        itr& operator++() { return m_cnt += m_step, *this; }
        int m_cnt, m_step;
    };
    int m_start, m_end, m_step;
public:
    range(const int start, const int end, const int step = 1) : m_start{start}, m_end{end}, m_step{step}
    {
        assert(m_step != 0);
        if (m_step > 0) { m_end = m_start + std::max(m_step - 1, m_end - m_start + m_step - 1) / m_step * m_step; }
        if (m_step < 0) { m_end = m_start - std::max(-m_step - 1, m_start - m_end - m_step - 1) / (-m_step) * (-m_step); }
    }
    itr begin() const { return itr{m_start, m_step}; }
    itr end() const { return itr{m_end, m_step}; }
};
range rep(const int end, const int step = 1) { return range(0, end, step); }
range per(const int rend, const int step = -1) { return range(rend - 1, -1, step); }
#pragma COMMENT "https://prng.di.unimi.it"
namespace xoshiro_impl {
u64 x;
u64 next()
{
    uint64_t z = (x += 0x9e3779b97f4a7c15);
    return z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9, z = (z ^ (z >> 27)) * 0x94d049bb133111eb, z ^ (z >> 31);
}
}
class Xoshiro32
{
public:
    using result_type = u32;
    Xoshiro32(result_type seed = 0) { xoshiro_impl::x = seed, s[0] = xoshiro_impl::next(), s[1] = xoshiro_impl::next(), s[2] = xoshiro_impl::next(), s[3] = xoshiro_impl::next(); }
    static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
    static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
    result_type operator()() { return next(); }
private:
    static inline result_type rotl(const result_type x, int k) { return (x << k) | (x >> (32 - k)); }
    result_type next()
    {
        const result_type result = rotl(s[1] * 5, 7) * 9, t = s[1] << 9;
        return s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t, s[3] = rotl(s[3], 11), result;
    }
    result_type s[4];
};
class Xoshiro64
{
public:
    using result_type = u64;
    Xoshiro64(result_type seed = 0) { xoshiro_impl::x = seed, s[0] = xoshiro_impl::next(), s[1] = xoshiro_impl::next(), s[2] = xoshiro_impl::next(), s[3] = xoshiro_impl::next(); }
    static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
    static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
    result_type operator()() { return next(); }
private:
    static inline result_type rotl(const result_type x, int k) { return (x << k) | (x >> (64 - k)); }
    result_type next()
    {
        const result_type result = rotl(s[1] * 5, 7) * 9, t = s[1] << 17;
        return s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t, s[3] = rotl(s[3], 45), result;
    }
    result_type s[4];
};
template<typename Rng>
class RNG
{
public:
    using result_type = typename Rng::result_type;
    static constexpr result_type min() { return Rng::min(); }
    static constexpr result_type max() { return Rng::max(); }
    RNG() : RNG(std::random_device{}()) {}
    RNG(const std::random_device::result_type seed) : m_rng(seed) {}
    result_type operator()() { return m_rng(); }
    template<typename T> T val(T min, T max) { return std::uniform_int_distribution<T>(min, max)(m_rng); }
    template<typename T> std::pair<T, T> pair(T min, T max) { return std::minmax({val<T>(min, max), val<T>(min, max)}); }
    template<typename T> std::vector<T> vec(int n, T min, T max) { return genVec<T>(n, [&]() { return val<T>(min, max); }); }
private:
    Rng m_rng;
};
RNG<std::mt19937> rng;
RNG<std::mt19937_64> rng64;
RNG<Xoshiro32> rng_xo;
RNG<Xoshiro64> rng_xo64;
class printer
{
public:
    printer(std::ostream& os = std::cout) : m_os{os} { m_os << std::fixed << std::setprecision(15); }
    template<typename... Args> int operator()(const Args&... args) { return dump(args...), 0; }
    template<typename... Args> int ln(const Args&... args) { return dump(args...), m_os << '\n', 0; }
    template<typename... Args> int el(const Args&... args) { return dump(args...), m_os << std::endl, 0; }
private:
    template<typename T> void dump(const T& v) { m_os << v; }
    template<typename T> void dump(const Vec<T>& vs) { for (int i = 0; i < (int)vs.size(); i++) { m_os << (i ? " " : ""), dump(vs[i]); } }
    template<typename T> void dump(const Vec<Vec<T>>& vss) { for (int i = 0; i < (int)vss.size(); i++) { m_os << (0 <= i or i + 1 < (int)vss.size() ? "\n" : ""), dump(vss[i]); } }
    template<typename T, typename... Ts> int dump(const T& v, const Ts&... args) { return dump(v), m_os << ' ', dump(args...), 0; }
    std::ostream& m_os;
};
printer out;
class scanner
{
public:
    scanner(std::istream& is = std::cin) : m_is{is} { m_is.tie(nullptr), std::ios::sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return m_is >> v, v;
    }
    template<typename T> T val(const T offset) { return val<T>() - offset; }
    template<typename T> std::vector<T> vec(const int n) { return genVec<T>(n, [this]() { return val<T>(); }); }
    template<typename T> std::vector<T> vec(const int n, const T offset) { return genVec<T>(n, [this, offset]() { return val<T>(offset); }); }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1) { return genVec<std::vector<T>>(n0, [this, n1]() { return vec<T>(n1); }); }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset) { return genVec<std::vector<T>>(n0, [this, n1, offset]() { return vec<T>(n1, offset); }); }
    template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }
    template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }
private:
    std::istream& m_is;
};
scanner in;
template<typename T>
class Zipper
{
public:
    Zipper() {}
    Zipper(const Vec<T>& vs) : m_vs(vs),
                               m_calced(false) {}
    T unzip(int n) { return assert(0 <= n and n < (int)m_vs.size()), calc(), m_vs[n]; }
    int zip(T v) { return calc(), std::lower_bound(m_vs.begin(), m_vs.end(), v) - m_vs.begin(); }
    void add(T v) { m_vs.push_back(v), m_calced = false; }
    void add(const std::vector<T>& vs)
    {
        for (const auto v : vs) { m_vs.push_back(v); }
        m_calced = false;
    }
    int size() { return calc(), (int)m_vs.size(); }
private:
    void calc()
    {
        if (not m_calced) { std::sort(m_vs.begin(), m_vs.end()), m_vs.erase(std::unique(m_vs.begin(), m_vs.end()), m_vs.end()), m_calced = true; }
    }
    Vec<T> m_vs;
    bool m_calced = true;
};
class UnionFind
{
public:
    UnionFind(const int sz) : m_sz{sz}, m_rt_or_size(m_sz, -1) { ; }
    int root_of(const int a) { return m_rt_or_size[a] < 0 ? a : m_rt_or_size[a] = root_of(m_rt_or_size[a]); }
    bool unite(int a, int b)
    {
        assert(a < m_sz), assert(b < m_sz), a = root_of(a), b = root_of(b);
        if (a == b) { return false; }
        if (-m_rt_or_size[a] < -m_rt_or_size[b]) { std::swap(a, b); }
        return m_rt_or_size[a] += m_rt_or_size[b], m_rt_or_size[b] = a, true;
    }
    int size_of(const int a) { return assert(a < m_sz), -m_rt_or_size[root_of(a)]; }
private:
    int m_sz;
    Vec<int> m_rt_or_size;
};
int main()
{
    const auto N = in.val<int>();
    Vec<f80> xs(N), ys(N), as(N);
    for (const int i : rep(N)) { std::tie(xs[i], ys[i], as[i]) = in.tup<f80, f80, f80>(); }
    Vec<f80> Xs(1 << N);
    for (const int m : rep(1 << N)) {
        f80 S = 0;
        using E = Pair<f80, Pair<int, int>>;
        std::vector<E> es;
        for (const int i : rep(N)) {
            if (btest(m, i)) {
                S += as[i];
                for (const int j : rep(i)) {
                    if (btest(m, j)) { es.push_back({std::hypot(xs[i] - xs[j], ys[i] - ys[j]), {i, j}}); }
                }
            }
        }
        std::sort(es.begin(), es.end());
        UnionFind uf(N);
        f80 D = 0;
        for (const auto e : es) {
            const auto c = e.first;
            const auto [i, j] = e.second;
            if (uf.root_of(i) != uf.root_of(j)) {
                D += c;
                uf.unite(i, j);
            }
        }
        Xs[m] = (S - D) / popcount(m);
    }
    auto dp = ndVec<f80>({1 << N}, -1e100);
    dp[0] = 1e100;
    for (const int m : range(1, 1 << N)) {
        for (int dm = m;; dm = (dm - 1) & m) {
            if (dm == 0) { break; }
            const int pm = m ^ dm;
            chmax(dp[m], std::min(Xs[dm], dp[pm]));
        }
    }
    out.ln(dp[(1 << N) - 1]);
    return 0;
}

Submission Info

Submission Time
Task E - Water Distribution
User pachicobue
Language C++ (GCC 9.2.1)
Score 1000
Code Size 13111 Byte
Status AC
Exec Time 159 ms
Memory 4380 KB

Compile Error

./Main.cpp:124: warning: ignoring #pragma COMMENT  [-Wunknown-pragmas]
  124 | #pragma COMMENT "https://prng.di.unimi.it"
      | 

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 46
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 155 ms 4304 KB
001.txt AC 153 ms 4372 KB
002.txt AC 152 ms 4352 KB
003.txt AC 153 ms 4356 KB
004.txt AC 155 ms 4344 KB
005.txt AC 152 ms 4376 KB
006.txt AC 154 ms 4332 KB
007.txt AC 152 ms 4340 KB
008.txt AC 154 ms 4348 KB
009.txt AC 153 ms 4372 KB
010.txt AC 152 ms 4352 KB
011.txt AC 154 ms 4380 KB
012.txt AC 150 ms 4352 KB
013.txt AC 150 ms 4372 KB
014.txt AC 151 ms 4352 KB
015.txt AC 155 ms 4312 KB
016.txt AC 151 ms 4352 KB
017.txt AC 153 ms 4348 KB
018.txt AC 151 ms 4344 KB
019.txt AC 149 ms 4336 KB
020.txt AC 152 ms 4376 KB
021.txt AC 152 ms 4380 KB
022.txt AC 152 ms 4348 KB
023.txt AC 155 ms 4340 KB
024.txt AC 153 ms 4336 KB
025.txt AC 155 ms 4352 KB
026.txt AC 155 ms 4344 KB
027.txt AC 150 ms 4356 KB
028.txt AC 156 ms 4352 KB
029.txt AC 154 ms 4380 KB
030.txt AC 157 ms 4380 KB
031.txt AC 158 ms 4376 KB
032.txt AC 154 ms 4348 KB
033.txt AC 157 ms 4316 KB
034.txt AC 155 ms 4300 KB
035.txt AC 159 ms 4372 KB
036.txt AC 155 ms 4312 KB
037.txt AC 155 ms 4316 KB
038.txt AC 155 ms 4316 KB
039.txt AC 156 ms 4372 KB
040.txt AC 2 ms 3792 KB
041.txt AC 2 ms 3700 KB
042.txt AC 2 ms 3836 KB
043.txt AC 3 ms 3748 KB
example0.txt AC 2 ms 3804 KB
example1.txt AC 153 ms 4344 KB