QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#42329 | #4433. Kitten and Roomba | antiravel | AC ✓ | 1712ms | 125804kb | C++23 | 9.1kb | 2022-08-01 22:29:16 | 2022-08-01 22:29:45 |
Judging History
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() - 1;
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: 100
Accepted
time: 1212ms
memory: 103228kb
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:
5.609417341486714 5.610505139292532
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 132ms
memory: 22968kb
input:
3 3 3 2 1 2 3 4000000 2 1 2 1 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 1 2 3 2 3 2 1 2 3 2 3 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 1 2 3 2 3 2 1 2 3 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 1 2 ...
output:
2000496.597369208233431 4999999.000000000000000 666788.777175006107427
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 303ms
memory: 4400kb
input:
5050 178 146 7 29 45 132 140 19 48 80 50 147 24 98 176 94 45 124 3 161 36 94 4 33 24 81 94 123 4 15 12 170 152 95 55 152 24 131 94 32 121 150 37 167 146 80 65 152 99 150 24 60 8 29 5 163 64 50 93 67 19 13 24 153 80 152 29 120 67 59 138 48 5 17 19 35 94 116 57 142 80 53 6 45 29 80 150 40 47 161 62 94...
output:
3.474522174310211 2.125000000000000 23.954963507657428 0.000000000000000 2.500000000000000 3.935962624587740 3.106841545495521 5.588792516971199 3.106619646407453 1.791666666666667 5.555530717631578 0.000000000000000 4.868330775897008 3.499328721323426 0.000000000000000 3.106851919765399 5.672871589...
result:
ok 5050 numbers
Test #4:
score: 0
Accepted
time: 1101ms
memory: 103064kb
input:
2 1000000 315562 679816 923554 749026 119526 400361 398944 729861 38631 237682 984276 240713 304346 923009 28429 705303 35145 281546 196216 128884 76719 542097 696978 832261 79936 617939 739512 639643 738806 304260 52873 63627 552308 627252 842013 683909 619035 326617 406438 159332 82575 823300 4115...
output:
4.452640912528094 4.446637996859227
result:
ok 2 numbers
Test #5:
score: 0
Accepted
time: 1136ms
memory: 103080kb
input:
2 1000000 315562 575035 646638 803204 719085 692015 374086 755314 193304 776395 55874 976706 805712 217914 823156 919201 953003 149774 16297 569437 50630 191605 6485 126613 286636 24494 152244 160536 434534 692015 362579 892731 521828 374895 872623 583943 946248 226984 256881 130161 826314 247361 45...
output:
5.837554136541755 4.271576397399082
result:
ok 2 numbers
Test #6:
score: 0
Accepted
time: 1712ms
memory: 125804kb
input:
2 1000000 941595 260117 135833 814046 740606 747365 965295 391550 71159 728551 704248 786875 854209 980320 968654 685130 721737 464879 19066 485673 803636 761076 467129 693561 787751 69739 373415 994214 367199 13100 494671 996272 547209 992937 103917 484331 476434 493297 779246 882922 78092 622726 3...
output:
8.814814814814817 11.332096366378158
result:
ok 2 numbers
Extra Test:
score: 0
Extra Test Passed