Submission #842499

#TimeUsernameProblemLanguageResultExecution timeMemory
842499BenqClosing Time (IOI23_closing)C++17
100 / 100
163 ms39192 KiB
#include "closing.h" #include <vector> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; #define mp make_pair #define f first #define s second #define tcT template <class T #define tcTU tcT, class U // ^ lol this makes everything look weird but I'll try it tcT > using V = vector<T>; tcT, size_t SZ > using AR = array<T, SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pi>; using vpl = V<pl>; using vpd = V<pd>; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); } tcT > int upb(V<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); } // loops #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define rep(a) F0R(_, a) #define each(a, x) for (auto &a : x) const int MOD = (int)1e9 + 7; // 998244353; const int MX = (int)2e5 + 5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!! mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; // bitwise ops // also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until // USACO updates ... return x == 0 ? 0 : 31 - __builtin_clz(x); } // floor(log2(x)) constexpr int p2(int x) { return 1 << x; } constexpr int msk2(int x) { return p2(x) - 1; } ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down tcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b) tcTU > T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); // assuming f is increasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; } tcTU > T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); // assuming f is decreasing while (lo < hi) { // find first index such that f is true T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; } tcT > void remDup(vector<T> &v) { // sort and remove duplicates sort(all(v)); v.erase(unique(all(v)), end(v)); } tcTU > void safeErase(T &t, const U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); } inline namespace IO { #define SFINAE(x, ...) \ template <class, class = void> struct x : std::false_type {}; \ template <class T> struct x<T, std::void_t<__VA_ARGS__>> : std::true_type {} SFINAE(DefaultI, decltype(std::cin >> std::declval<T &>())); SFINAE(DefaultO, decltype(std::cout << std::declval<T &>())); SFINAE(IsTuple, typename std::tuple_size<T>::type); SFINAE(Iterable, decltype(std::begin(std::declval<T>()))); template <class T> constexpr char Space(const T &) { return (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' '; } template <auto &is> struct Reader { template <class T> void Impl(T &t) { if constexpr (DefaultI<T>::value) is >> t; else if constexpr (Iterable<T>::value) { for (auto &x : t) Impl(x); } else if constexpr (IsTuple<T>::value) { std::apply([this](auto &...args) { (Impl(args), ...); }, t); } else static_assert(IsTuple<T>::value, "No matching type for read"); } template <class... Ts> void read(Ts &...ts) { ((Impl(ts)), ...); } }; template <class... Ts> void re(Ts &...ts) { Reader<cin>{}.read(ts...); } #define def(t, args...) \ t args; \ re(args); template <auto &os, bool debug> struct Writer { string comma() const { return debug ? "," : ""; } template <class T> void Impl(T const &t) const { if constexpr (DefaultO<T>::value) os << t; else if constexpr (Iterable<T>::value) { if (debug) os << '{'; int i = 0; for (auto &&x : t) ((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x)); if (debug) os << '}'; } else if constexpr (IsTuple<T>::value) { if (debug) os << '('; std::apply( [this](auto const &...args) { int i = 0; (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)), ...); }, t); if (debug) os << ')'; } else static_assert(IsTuple<T>::value, "No matching type for print"); } template <class T> void ImplWrapper(T const &t) const { if (debug) os << "\033[0;31m"; Impl(t); if (debug) os << "\033[0m"; } template <class... Ts> void print(Ts const &...ts) const { ((Impl(ts)), ...); } template <class F, class... Ts> void print_with_sep(const std::string &sep, F const &f, Ts const &...ts) const { ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n'; } void print_with_sep(const std::string &) const { os << '\n'; } }; template <class... Ts> void pr(Ts const &...ts) { Writer<cout, false>{}.print(ts...); } template <class... Ts> void ps(Ts const &...ts) { Writer<cout, false>{}.print_with_sep(" ", ts...); } } // namespace IO inline namespace Debug { template <typename... Args> void err(Args... args) { Writer<cerr, true>{}.print_with_sep(" | ", args...); } void err_prefix(str func, int line, string args) { cerr << "\033[0;31m\u001b[1mDEBUG\033[0m" << " | " << "\u001b[34m" << func << "\033[0m" << ":" << "\u001b[34m" << line << "\033[0m" << " - " << "[" << args << "] = "; } #ifdef LOCAL #define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args) #else #define dbg(...) #endif const auto beg_time = std::chrono::high_resolution_clock::now(); // https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1 double time_elapsed() { return chrono::duration<double>(std::chrono::high_resolution_clock::now() - beg_time) .count(); } } // namespace Debug inline namespace FileIO { void setIn(str s) { freopen(s.c_str(), "r", stdin); } void setOut(str s) { freopen(s.c_str(), "w", stdout); } void setIO(str s = "") { cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams cout << fixed << setprecision(12); // cin.exceptions(cin.failbit); // throws exception when do smth illegal // ex. try to read letter into int if (sz(s)) setIn(s + ".in"), setOut(s + ".out"); // for old USACO } } // namespace FileIO /** * Description: wraps a lambda so it can call itself * Source: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html */ namespace std { template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {} template <class... Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template <class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); } } // namespace std void y_comb_demo() { cout << y_combinator([](auto gcd, int a, int b) -> int { return b == 0 ? a : gcd(b, a % b); })(20, 30) << "\n"; // outputs 10 } int solve(vl ones, vpl _twos, ll K) { vpl twos; each(t, _twos) { if (2 * t.f <= t.s) { ones.pb(t.f); ones.pb(t.s - t.f); } else { twos.pb({t.s, t.f}); } } vl dp1{0}; { sor(ones); each(t, ones) dp1.pb(dp1.bk + t); } sor(twos); vl dp2(2 * sz(twos) + 1, BIG); vl min_first; { ll mn = BIG; min_first.rsz(sz(twos)); R0F(i, sz(twos)) { ckmin(mn, twos[i].s); min_first[i] = mn; } } // dbg(min_first); { ll sum = 0; ll max_sec = 0; F0R(i, sz(twos) + 1) { if (i) { sum += twos.at(i - 1).f; ckmax(max_sec, twos.at(i - 1).f - twos.at(i - 1).s); ckmin(dp2.at(2 * i - 1), sum - max_sec); } if (i < sz(twos)) { ckmin(dp2.at(2 * i + 1), sum + min_first.at(i)); } dp2.at(2 * i) = sum; } } return lstTrue(0, sz(dp1) + sz(dp2) - 2, [&](int x) { F0R(i, sz(dp1)) { int j = x - i; if (0 <= j && j < sz(dp2) && dp1[i] + dp2[j] <= K) return true; } return false; }); // int ans = 0; // F0R(i, sz(dp1)) F0R(j, sz(dp2)) if (dp1[i] + dp2[j] <= K) ckmax(ans, i + // j); // // dbg(ones, twos, K, dp1, dp2, ans); // return ans; } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> _V, std::vector<int> W) { AR<vl, 2> dist{vl(N), vl(N)}; V<vpi> adj(N); F0R(i, N - 1) { adj[U[i]].pb({_V[i], W[i]}); adj[_V[i]].pb({U[i], W[i]}); } auto gen_dist = y_combinator([&](auto self, int i, int x, int p) -> void { for (auto [y, w] : adj[x]) if (y != p) { dist.at(i).at(y) = dist.at(i).at(x) + w; self(i, y, x); } }); gen_dist(0, X, -1); gen_dist(1, Y, -1); int ans1 = 0; { priority_queue<ll, vl, greater<ll>> pq; F0R(i, 2) F0R(j, N) pq.push(dist[i][j]); ll K1 = K; while (sz(pq) && K1 >= pq.top()) { K1 -= pq.top(); pq.pop(); ++ans1; } } int ans2 = [&]() { ll dist_between = dist[0].at(Y); vl ones; vpl twos; int cnt = 0; F0R(i, N) { if (dist[0][i] + dist[1][i] == dist_between) { K -= min(dist[0][i], dist[1][i]); ++cnt; ones.pb(max(dist[0][i], dist[1][i]) - min(dist[0][i], dist[1][i])); } else { twos.pb( {min(dist[0][i], dist[1][i]), max(dist[0][i], dist[1][i])}); } } if (K < 0) return 0; return cnt + solve(ones, twos, K); }(); // dbg(ans1, ans2); return max(ans1, ans2); }

Compilation message (stderr)

closing.cpp: In function 'void FileIO::setIn(str)':
closing.cpp:246:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 | void setIn(str s) { freopen(s.c_str(), "r", stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
closing.cpp: In function 'void FileIO::setOut(str)':
closing.cpp:247:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 | void setOut(str s) { freopen(s.c_str(), "w", stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...