제출 #849584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
849584		skittles1412	봉쇄 시간 (IOI23_closing)	C++17	75 / 100	1062 ms	71272 KiB

closing

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename Cb>
struct Cmp {
    Cb cb;

    Cmp(Cb cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

vector<vector<pair<int, long>>> edges_to_adj(
    int n,
    const vector<tuple<int, int, long>>& edges) {
    vector<vector<pair<int, long>>> graph(n);

    for (auto& [u, v, w] : edges) {
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    return graph;
}

struct DistDFS {
    vector<long> dist;
    vector<vector<pair<int, long>>> graph;

    DistDFS(int root, int n, const vector<tuple<int, int, long>>& edges)
        : dist(n), graph(edges_to_adj(n, edges)) {
        dfs(root, -1, 0);
    }

    void dfs(int u, int p, long d) {
        dist[u] = d;

        for (auto& [v, w] : graph[u]) {
            if (v == p) {
                continue;
            }

            dfs(v, u, d + w);
        }
    }
};

struct PathDFS {
    int n;
    vector<int> path;
    vector<char> on_path;
    vector<vector<int>> path_subs;
    vector<vector<pair<int, long>>> graph;

    PathDFS(int u0, int u1, int n, const vector<tuple<int, int, long>>& edges)
        : n(n), on_path(n), graph(edges_to_adj(n, edges)) {
        pdfs(u0, -1, u1);

        for (auto& a : path) {
            on_path[a] = true;
        }

        for (auto& a : path) {
            path_subs.emplace_back();
            dfs(a, -1, path_subs.back());
        }
    }

    vector<int> st;

    void pdfs(int u, int p, int targ) {
        st.push_back(u);

        if (u == targ) {
            path = st;
        }

        for (auto& [v, _w] : graph[u]) {
            if (v == p) {
                continue;
            }

            pdfs(v, u, targ);
        }

        st.pop_back();
    }

    void dfs(int u, int p, vector<int>& out) {
        out.push_back(u);

        for (auto& [v, _w] : graph[u]) {
            if (v == p || on_path[v]) {
                continue;
            }

            dfs(v, u, out);
        }
    }
};

struct DS {
    multiset<long> v[2];

    void insert(int ind, long x) {
        dbg("+", ind, x);
        v[ind].insert(x);
    }

    void erase(int ind, long x) {
        dbg("-", ind, x);
        assert(v[ind].find(x) != v[ind].end());
        v[ind].erase(v[ind].find(x));
    }

    int query(long kv) {
        vector<long> ps0 {0}, ps1 {0};

        for (auto& a : v[0]) {
            ps0.push_back(ps0.back() + a);
        }
        for (auto& a : v[1]) {
            ps1.push_back(ps1.back() + a);
        }

        int ans = -1e9;

        for (int i = 0, j = sz(ps1) - 1; i < sz(ps0); i++) {
            for (; j >= 0 && ps0[i] + ps1[j] > kv; j--)
                ;
            if (j < 0) {
                break;
            }

            ans = max(ans, 2 * i + j);
        }

        return ans;
    }
};

int solve_disjoint(long kv,
                   const vector<long>& dist0,
                   const vector<long>& dist1) {
    vector<long> dists;
    dists.insert(dists.end(), begin(dist0), end(dist0));
    dists.insert(dists.end(), begin(dist1), end(dist1));

    sort(begin(dists), end(dists));

    long sum = 0;
    int i;
    for (i = 0; i < sz(dists); i++) {
        sum += dists[i];
        if (sum > kv) {
            break;
        }
    }

    return i;
}

int solve(int n, int u0, int u1, long kv, vector<tuple<int, int, long>> edges) {
    auto dist0 = DistDFS(u0, n, edges).dist, dist1 = DistDFS(u1, n, edges).dist;
    auto path_dfs = PathDFS(u0, u1, n, edges);
    auto path = path_dfs.path_subs;
    int m = sz(path);

    vector<long> cost1(n), cost2(n), delta(n);

    for (int i = 0; i < n; i++) {
        cost1[i] = min(dist0[i], dist1[i]);
        cost2[i] = max(dist0[i], dist1[i]);
        delta[i] = cost2[i] - cost1[i];
    }

    map<long, vector<int>> mp;

    for (int i = 0; i < m; i++) {
        mp[delta[path[i][0]]].push_back(i);
    }

    DS ds;

    int ans = solve_disjoint(kv, dist0, dist1);
    dbg(ans);

    int ans_add = 0;
    long min_cost = 0;
    for (auto& a : path_dfs.path) {
        ans_add++;
        min_cost += cost1[a];
    }

    auto move_vals = [&](vector<int> nodes, bool undo) -> void {
        sort(begin(nodes), end(nodes),
             Cmp([&](int u) -> long { return cost1[u]; }));

        for (auto& u : nodes) {
            if (path_dfs.on_path[u]) {
                ans_add++;
                min_cost += delta[u];
            } else {
                ds.erase(1, cost1[u]);
                ds.insert(0, cost2[u]);
            }

            ans = max(ans, ans_add + ds.query(kv - min_cost));
            dbg(ans, ans_add, min_cost);
        }

        if (!undo) {
            return;
        }

        for (auto& u : nodes) {
            if (path_dfs.on_path[u]) {
                ans_add--;
                min_cost -= delta[u];
            } else {
                ds.insert(1, cost1[u]);
                ds.erase(0, cost2[u]);
            }
        }
    };

    for (int i = 0; i < n; i++) {
        if (path_dfs.on_path[i]) {
            continue;
        }
        ds.insert(1, cost1[i]);
    }

    for (auto& [_k, vals] : mp) {
        dbg(vals);
        if (sz(vals) == 1) {
            move_vals(path[vals[0]], false);
            continue;
        }

        assert(sz(vals) == 2);
        dbg(ans_add, min_cost);
        move_vals(path[vals[0]], true);
        dbg(ans_add, min_cost);
        move_vals(path[vals[1]], false);
        move_vals(path[vals[0]], false);
    }

    return ans;
}

int max_score(int n,
              int u0,
              int u1,
              ll kv,
              vector<int> edges_u,
              vector<int> edges_v,
              vector<int> edges_w) {
    vector<tuple<int, int, long>> edges;

    for (int i = 0; i < n - 1; i++) {
        edges.emplace_back(edges_u[i], edges_v[i], edges_w[i]);
    }

    return solve(n, u0, u1, kv, edges);
}

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