QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#42327#4433. Kitten and RoombaantiravelWA 1808ms103160kbC++239.1kb2022-08-01 22:27:332022-08-01 22:27:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-01 22:27:54]
  • 评测
  • 测评结果:WA
  • 用时:1808ms
  • 内存:103160kb
  • [2022-08-01 22:27:33]
  • 提交

answer


#include <algorithm>
#include <bitset>
#include <cinttypes>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace impl
{

inline void force_templates()
{
#define FORCE(type)                                                            \
  {                                                                            \
    [[maybe_unused]] auto f = [] type {};                                      \
  }

  FORCE((std::pair<int, int>))
  FORCE((std::vector<int>))
  FORCE((std::vector<std::pair<int, int>>))

#undef FORCE
}

} // namespace impl


#include <iostream>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>

namespace cm
{


class logger
{
public:
  logger(std::ostream &) {}
  logger &set_ostream(std::ostream &)
  {
    return *this;
  }
  logger &set_sep(const std::string &)
  {
    return *this;
  }
  logger &assert_push_enable()
  {
    return *this;
  }
  logger &assert_push_disable()
  {
    return *this;
  }
  logger &assert_exit()
  {
    return *this;
  }
  logger &assert_noexit()
  {
    return *this;
  }
  logger &endl()
  {
    return *this;
  }
  template <class... T>
  logger &log(T...)
  {
    return *this;
  }
  template <class T>
  logger &hint(T...)
  {
    return *this;
  }
  template <class... T>
  logger &operator()(T...)
  {
    return *this;
  }
  template <class... T>
  logger &assert_(T...)
  {
    return *this;
  }
};


namespace impl
{
logger cm_logger(std::cout);
}

} // namespace cm

// clang-format off
#define see(...)
#define asee(...)
#define cm_assert(...)
// clang-format on

// #include "/home/jack/cm/intm.hpp"
// #include "/home/jack/cm/math_util.hpp"

#include <cctype>
#include <cstdio>

namespace cm
{

template <class _Type, size_t _buf_size>
class buffer_reader
{
protected:
  FILE        *src;
  _Type *const buff;
  _Type       *buff_end;
  _Type       *buff_pos;

  void _flush()
  {
    buff_end = buff + fread(buff, sizeof(_Type), _buf_size, src);
    buff_pos = buff;
    if (buff_end == buff)
    {
      *buff_end = '\n';
      buff_end++;
    }
  }

public:
  explicit buffer_reader(FILE *_src) : src(_src), buff(new _Type[_buf_size])
  {
    _flush();
  }

  buffer_reader(const buffer_reader &) = delete;
  buffer_reader(buffer_reader &&)      = delete;
  buffer_reader &operator=(const buffer_reader &) = delete;
  buffer_reader &operator=(buffer_reader &&) = delete;

  _Type get() const
  {
    return *buff_pos;
  }
  _Type next()
  {
    _Type result = get();
    buff_pos++;
    if (buff_pos == buff_end)
      _flush();
    return result;
  }

  ~buffer_reader()
  {
    if (src != stdin)
      fclose(src);
    delete[] buff;
  }
};

template <class _BufferReader>
class scanner : protected _BufferReader
{
private:
  using _BufferReader::get;
  using _BufferReader::next;
  inline bool _is_ws(char c)
  {
    return c <= ' ';
  }
  inline bool _is_cr(char c)
  {
    return c == '\n' || c == '\r';
  }

  int _get_sign()
  {
    while (!isdigit(get()) && get() != '-')
      next();
    if (get() == '-')
      return next(), -1;
    return 1;
  }

public:
  scanner() = delete;
  using _BufferReader::_BufferReader;

  char next_char()
  {
    while (_is_ws(get()))
      next();
    return next();
  }

  char *next_token(char *s)
  {
    while (_is_ws(get()))
      next();
    while (!_is_ws(get()))
      *s++ = next();
    *s = '\0';
    return s;
  }

  char *next_line(char *s)
  {
    while (_is_ws(get()))
      next();
    while (!_is_cr(get()))
      *s++ = next();
    *s = '\0';
    return s;
  }

  template <class _Integer>
  _Integer next_integer()
  {
    _Integer sign = _get_sign();
    _Integer result(0);
    while (isdigit(get()))
      result = result * _Integer(10) + _Integer(next() - '0');
    return sign * result;
  }

  int next_int()
  {
    return next_integer<int>();
  }

  long long next_long()
  {
    return next_integer<long long>();
  }

  double next_double()
  {
    int    sign   = _get_sign();
    double result = 0;
    while (isdigit(get()))
      result = result * 10 + (next() - '0');
    if (get() == '.')
    {
      next();
      double cur_ep = 0.1;
      while (isdigit(get()))
        result += cur_ep * (next() - '0'), cur_ep *= 0.1;
    }
    return sign * result;
  }
};

} // namespace cm


namespace cm
{
using optimal_reader = buffer_reader<char, 1 << 16>;
}

#define DEFINE_SCANNER(sc, filename)                                           \
  cm::scanner<cm::optimal_reader> sc(fopen(filename, "r"));


// #include "/home/jack/cm/segment_tree.hpp"
// #include "/home/jack/cm/string.hpp"

#include <array>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

namespace cm
{

template <class T>
inline bool check_min(T &a, const T &b)
{
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool check_max(T &a, const T &b)
{
  return a < b ? a = b, 1 : 0;
}

struct once_t
{
  bool _once = true;
  bool operator()()
  {
    return _once ? (_once = false, true) : false;
  }
};

template <class T, class vt = std::vector<std::vector<T>>>
vt vec_transpose(const vt &v)
{
  size_t n = v.size();
  size_t m = v[0].size();


  vt r(m, std::vector<T>(n));
  for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < m; j++)
      r[j][i] = v[i][j];

  return r;
}

template <class value_type = int>
struct counter_t
{
private:
  value_type _value{};

public:
  value_type operator()()
  {
    return _value++;
  }

  value_type size() const
  {
    return _value;
  }

  void clear()
  {
    _value = value_type{};
  }
};

namespace impl
{
template <class T, std::size_t n0, std::size_t... n1>
struct __array
{
  using type = std::array<typename __array<T, n1...>::type, n0>;
};

template <class T, std::size_t n0>
struct __array<T, n0>
{
  using type = std::array<T, n0>;
};

} // namespace impl

template <class T, std::size_t... n0>
using array = typename impl::__array<T, n0...>::type;

#if __cplusplus >= 201402L

template <class F>
struct y_combinate_t
{
  F f;

  template <class... Args>
  decltype(auto) operator()(Args &&...args) const
  {
    return f(*this, std::forward<Args>(args)...);
  }
};

template <class F>
y_combinate_t<std::decay_t<F>> y_combinate(F &&f)
{
  return {std::forward<F>(f)};
};

auto vec_take(size_t id)
{
  return [id](const auto &v) { return v[id]; };
}

template <class F, class... T>
auto vec_map(F &&f, const std::vector<T> &...v)
{
  using mapped_t = decltype(f(std::declval<T>()...));

  std::size_t n = [](auto x, auto...) { return x; }(v.size()...);

  std::vector<mapped_t> r;
  r.reserve(n);

  cm::y_combinate([&](auto &&self, std::size_t cnt, auto... its) -> void {
    if (cnt > 0)
    {
      r.emplace_back(f((*its)...));
      self(cnt - 1, std::next(its)...);
    }
  })(n, v.begin()...);

  return r;
}

template <class F>
auto mapper(F &&f)
{
  return [f](auto v) { return vec_map(f, v); };
}

template <class T>
auto transfer(T &&v)
{
  return std::forward<T>(v);
}
template <class T, class F0, class... F1>
auto transfer(T &&v, F0 &&f0, F1 &&...f1)
{
  return transfer(f0(std::forward<T>(v)), f1...);
}

#endif

} // namespace cm

using cm::check_max;
using cm::check_min;

#define CONSTRAINT(n, a, b) constexpr auto n = a;

#include <vector>

cm::scanner<cm::optimal_reader> sc(stdin);

int main()
{
  int t = sc.next_int();
  for (int i = 0; i < t; i++)
  {
    int n = sc.next_int();
    int c = sc.next_int() - 1;

    std::vector<std::vector<int>> e(n);
    for (int i = 0; i < n - 1; i++)
    {
      int u = sc.next_int() - 1;
      int v = sc.next_int() - 1;
      e[u].push_back(v);
      e[v].push_back(u);
    }

    int m = sc.next_int();

    std::vector<int> path(m);
    for (int i = 0; i < m; i++)
      path[i] = sc.next_int();

    auto fa = [&] {
      std::vector<int> a(n);
      cm::y_combinate([&](auto &&self, int u, int f) -> void {
        a[u] = f;
        for (int v: e[u])
          if (v != f)
            self(v, u);
      })(0, -1);
      return a;
    }();

    std::vector<double> dpv(n, 0);
    std::vector<double> dps(n, 0);

    auto set_dpv = [&](int u, double v) {
      if (fa[u] != -1)
        dps[fa[u]] -= dpv[u];
      dpv[u] = v;
      if (fa[u] != -1)
        dps[fa[u]] += dpv[u];
    };

    auto get_dpr = [&](int u) {
      double res = dps[u];
      if (fa[u] != -1)
        res += dpv[fa[u]];
      return res;
    };

    for (int i = m - 1; i >= 0; i--)
    {
      int  u = path[i];
      auto w = get_dpr(u) / (double)e[u].size() + 1;
      set_dpv(u, w);
    }

    printf("%.15lf\n", dpv[c]);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1808ms
memory: 103160kb

input:

2
1000000 315562
969409 917725
324847 719085
524235 603427
576843 433171
75335 238378
266746 487233
80422 95099
594363 96140
858172 261406
958326 466109
233845 350950
863969 345645
689972 81395
395383 27274
93913 208983
523722 380358
108074 172341
130041 692304
737158 383812
752080 33646
154356 6672...

output:

1.000000000000000
2.166666666666667

result:

wrong answer 1st numbers differ - expected: '5.60942', found: '1.00000', error = '0.82173'