제출 #842457

#제출 시각아이디문제언어결과실행 시간메모리
842457Benq봉쇄 시간 (IOI23_closing)C++17
100 / 100
441 ms58920 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) { // dbg(ones, twos, K); set<pair<ll, int>> has, nxt1, nxt2; vi status(sz(ones) + sz(twos)); auto init = [&](int x) { if (x < sz(ones)) { nxt1.ins({ones[x], x}); } else { const int i = x - sz(ones); nxt1.ins({twos[i].f, i + sz(ones)}); nxt2.ins({twos[i].s, i + sz(ones)}); } }; F0R(i, sz(ones) + sz(twos)) init(i); int ans = 0; while (sz(nxt1) || sz(nxt2)) { ll tran1 = sz(nxt1) ? begin(nxt1)->f : BIG; ll tran2 = (sz(nxt2) && sz(has)) ? begin(nxt2)->f - rbegin(has)->f : BIG; ll tran = min(tran1, tran2); if (tran > K) return ans; K -= tran; ++ans; if (tran == tran1) { auto p = *begin(nxt1); nxt1.erase(p); has.ins(p); if (p.s >= sz(ones)) { // two if (status[p.s] == 0) { // one in has, one in nxt1, nothing in nxt2 safeErase(nxt2, pair<ll, int>{twos.at(p.s - sz(ones)).s, p.s}); nxt1.ins( {twos.at(p.s - sz(ones)).s - twos.at(p.s - sz(ones)).f, p.s}); // OK } else { // one in has, nothing in nxt1, nothing in nxt2 assert(status[p.s] == 1); safeErase(has, pair<ll, int>{twos.at(p.s - sz(ones)).f, p.s}); } } ++status[p.s]; } else { auto p = *begin(nxt2); auto q = *rbegin(has); assert(p.s != q.s); nxt2.erase(p); has.erase(q); { assert(status.at(p.s) == 0); status.at(p.s) += 2; { assert(p.s >= sz(ones)); safeErase(nxt1, pair<ll, int>{twos.at(p.s - sz(ones)).f, p.s}); has.ins(pair<ll, int>{twos.at(p.s - sz(ones)).s - twos.at(p.s - sz(ones)).f, p.s}); } } --status.at(q.s); if (q.s >= sz(ones)) { if (status[q.s] == 0) { // before: one in nxt1, one in has safeErase(nxt1, pair<ll, int>{twos.at(q.s - sz(ones)).s - twos.at(q.s - sz(ones)).f, q.s}); init(q.s); } else { // before: one in has, after: one in has, one in nxt1 has.ins({twos.at(q.s - sz(ones)).f, q.s}); nxt1.ins( {twos.at(q.s - sz(ones)).s - twos.at(q.s - sz(ones)).f, q.s}); } } else { init(q.s); } } } // dbg(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); }

컴파일 시 표준 에러 (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...