제출 #845174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845174		hamerin	경주 (Race) (IOI11_race)	C++17	43 / 100	3036 ms	102232 KiB

race

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using li = long long;
using ld = long double;
using pi = pair<int, int>;
using pli = pair<li, li>;

#define all(c) c.begin(), c.end()
#define prec(n) setprecision(n) << fixed

template <typename K, typename V>
class map_m : public map<K, V> {
   public:
    auto emplace_minimal(K k, V v) {
        auto [it, success] = this->try_emplace(k, v);
        if (!success && it->second > v) it->second = v;
        return it;
    }
};

class Tree {
   public:
    int V, R;
    vector<vector<pair<int, li>>> adj, tr;
    vector<int> sz, pr, ofl;
    vector<map_m<li, int>> mp;
    vector<li> ofw;

    explicit Tree(int _V)
        : V(_V), adj(V), tr(V), sz(V), pr(V), ofl(V), mp(V), ofw(V) {
        iota(all(pr), 0);
    }

    void emplace_edge(int u, int v, li w) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    void compile(int _R) {
        R = _R;

        function<void(int, optional<int>)> dfs = [&](int h, optional<int> p) {
            sz[h] = 1;

            for (auto [t, W] : adj[h]) {
                if (p && t == *p) continue;

                dfs(t, h);

                tr[h].emplace_back(t, W);
                if (sz[t] > sz[tr[h][0].first]) swap(tr[h][0], tr[h].back());
                sz[h] += sz[t];
            }

            if (!tr[h].empty()) pr[h] = pr[tr[h][0].first];

            adj[h].clear();
            adj[h].shrink_to_fit();
        };

        dfs(R, nullopt);
    }

    optional<int> solve(int h, li K) {
        optional<int> ret;
        multiset<pair<li, int>> courses;

        for (auto [t, W] : tr[h]) {
            auto sol = solve(t, K);

            if (sol) {
                if (!ret)
                    ret = sol;
                else
                    ret = min(*ret, *sol);
            }

            auto it = mp[pr[t]].find(K - W - ofw[pr[t]]);
            if (it != mp[pr[t]].end()) {
                if (!ret)
                    ret = ofl[pr[t]] + 1 + it->second;
                else
                    ret = min(*ret, ofl[pr[t]] + 1 + it->second);
            }

            it = mp[pr[t]].begin();
            while (it != mp[pr[t]].end()) {
                if (sol && it->second + ofl[pr[t]] + 1 > *sol) {
                    it = mp[pr[t]].erase(it);
                    continue;
                }

                ++it;
            }

            if (pr[h] != pr[t]) {
                for (auto [w, l] : mp[pr[t]])
                    courses.emplace(W + w + ofw[pr[t]], l + ofl[pr[t]] + 1);
            }
        }

        for (auto [t, W] : tr[h]) {
            if (pr[h] != pr[t]) {
                for (auto [w, l] : mp[pr[t]])
                    courses.erase({W + w + ofw[pr[t]], l + ofl[pr[t]] + 1});
            }

            for (auto [w, l] : mp[pr[t]]) {
                auto remain = K - W - w - ofw[pr[t]];
                if (remain < 0) break;

                auto it = courses.lower_bound({remain, -1});
                if (it != courses.end() && it->first == remain) {
                    if (!ret)
                        ret = l + ofl[pr[t]] + 1 + it->second;
                    else
                        ret = min(*ret, l + ofl[pr[t]] + 1 + it->second);
                }
            }

            if (pr[h] != pr[t]) {
                for (auto [w, l] : mp[pr[t]])
                    courses.emplace(W + w + ofw[pr[t]], l + ofl[pr[t]] + 1);
            }
        }

        if (h != pr[h]) {
            auto [t, W] = tr[h][0];
            for (auto [w, l] : mp[pr[t]])
                courses.emplace(W + w + ofw[pr[t]], l + ofl[pr[t]] + 1);

            ofw[pr[h]] += tr[h][0].second;
            ofl[pr[h]]++;
        }

        for (auto [t, W] : adj[h]) mp[pr[t]].clear();
        for (auto [w, l] : courses)
            mp[pr[h]].emplace_minimal(w - ofw[pr[h]], l - ofl[pr[h]]);
        mp[pr[h]].emplace_minimal(-ofw[pr[h]], -ofl[pr[h]]);

        auto it = mp[pr[h]].upper_bound(K - ofw[pr[h]]);
        mp[pr[h]].erase(it, mp[pr[h]].end());

        return ret;
    }
};

int best_path(int N, int K, int H[][2], int L[]) {
    Tree T(N);
    for (int i = 0; i < N - 1; i++) {
        T.emplace_edge(H[i][0], H[i][1], L[i]);
    }
    T.compile(0);
    auto res = T.solve(0, K);
    return res ? *res : -1;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57