제출 #958474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958474		876pol	Closing Time (IOI23_closing)	C++17	18 / 100	1059 ms	45180 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(a, c) for (const auto &a : c)
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << '[';
    for (auto it = obj.begin(); it != obj.end(); it++)
        out << &", "[2 * (it == obj.begin())] << *it;
    return out << ']';
}

int max_score(int N, int X, int Y, ll K, vec<int> U, vec<int> V, vec<int> W) {
    vec<vec<pll>> graph(N);
    FOR(i, 0, N - 1) {
        graph[U[i]].push_back({V[i], W[i]});
        graph[V[i]].push_back({U[i], W[i]});
    }
    vec<bool> in_path(N);
    vec<pll> path;
    function<bool(ll, ll)> dfs1 = [&](ll curr, ll prev) -> bool {
        if (curr == Y) return true;
        TRAV(e, graph[curr]) {
            if (e.first == prev) continue;
            in_path[e.first] = 1;
            path.push_back({e.first, path.back().second + e.second});
            if (dfs1(e.first, curr)) return true;
            in_path[e.first] = 0;
            path.pop_back();
        }
        return false;
    };
    in_path[X] = 1;
    path.push_back({X, 0});
    dfs1(X, -1);
    ll length = path.back().second;
    ll M = path.size();
    vec<vec<ll>> dist(M);
    FOR(i, 0, M) {
        function<void(ll, ll, ll)> dfs2 = [&](ll curr, ll prev, ll cdist) {
            dist[i].push_back(cdist);
            TRAV(e, graph[curr]) {
                if (e.first == prev || in_path[e.first]) continue;
                dfs2(e.first, curr, cdist + e.second);
            }
        };
        dfs2(path[i].first, -1, 0);
        sort(dist[i].begin(), dist[i].end());
    }
    // dbg(in_path);
    // dbg(path);
    // dbg(dist);
    ll best = 0;
    FOR(x, 0, M) {
        FOR(y, 0, M) {
            // [0, x] and [y, M - 1]
            ll ans = 0;
            ll curr = 0;
            multiset<pair<ll, pll>> ms1, ms2;
            CFOR(i, 0, min(x, y - 1)) {
                ans++;
                curr += path[i].second;
                for (auto it = dist[i].begin() + 1; it != dist[i].end(); it++) {
                    ms1.insert({path[i].second + *it, {-1, -1}});
                }
            }
            CFOR(i, max(x + 1, y), M - 1) {
                ans++;
                curr += length - path[i].second;
                for (auto it = dist[i].begin() + 1; it != dist[i].end(); it++) {
                    ms1.insert({length - path[i].second + *it, {-1, -1}});
                }
            }
            CFOR(i, y, x) {
                ll mn = min(path[i].second, length - path[i].second);
                ll mx = max(path[i].second, length - path[i].second);
                ans += 2;
                curr += mx;
                for (auto it = dist[i].begin() + 1; it != dist[i].end(); it++) {
                    ms1.insert({mn + *it, {mn + *it, mx - mn}});
                    ms2.insert({mx + *it, {mn + *it, mx - mn}});
                }
            }
            if (curr > K) continue;
            // dbg(ms1);
            // dbg(ms2);
            // dbg(curr);
            // dbg(ans);
            while (ms1.size() || ms2.size()) {
                auto take1 = [&]() {
                    auto tmp = *ms1.begin();
                    if (tmp.second != pll{-1, -1}) {
                        ms2.erase(
                            ms2.find({tmp.second.first + tmp.second.second,
                                      tmp.second}));
                        ms1.insert({tmp.second.second, {-1, -1}});
                    }
                    ms1.erase(ms1.find(tmp));
                    ans += 1;
                    curr += tmp.first;
                };
                auto take2 = [&]() {
                    auto tmp = *ms2.begin();
                    ms1.erase(ms1.find({tmp.second.first, tmp.second}));
                    ms2.erase(ms2.find(tmp));
                    ans += 2;
                    curr += tmp.first;
                };
                if (ms1.size() == 1) {
                    if (ms2.size() && curr + ms2.begin()->first <= K) {
                        take2();
                    } else if (curr + ms1.begin()->first <= K) {
                        take1();
                    } else {
                        break;
                    }
                } else {
                    if (ms2.size() &&
                        ms1.begin()->first + next(ms1.begin())->first >=
                            ms2.begin()->first &&
                        curr + ms2.begin()->first <= K) {
                        take2();
                    } else if (curr + ms1.begin()->first <= K) {
                        take1();
                    } else {
                        break;
                    }
                }
            }
            // dbg(x);
            // dbg(y);
            // dbg(ans);
            best = max(best, ans);
        }
        // cerr << x << endl;
    }
    return best;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17