#954721 (C++14) No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ

提出ソース

結果

問題	No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
ユーザー	umimel
提出日時	2024-02-23 23:16:41
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,323 ms / 2,000 ms
コード長	8,100 bytes
コンパイル時間	4,065 ms
コンパイル使用メモリ	200,712 KB
実行使用メモリ	53,472 KB
最終ジャッジ日時	2024-02-23 23:18:14
合計ジャッジ時間	69,540 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	556 ms 6,548 KB
testcase_02	AC	531 ms 6,548 KB
testcase_03	AC	564 ms 6,548 KB
testcase_04	AC	705 ms 7,944 KB
testcase_05	AC	730 ms 8,028 KB
testcase_06	AC	736 ms 8,132 KB
testcase_07	AC	902 ms 24,676 KB
testcase_08	AC	922 ms 24,684 KB
testcase_09	AC	958 ms 36,316 KB
testcase_10	AC	932 ms 35,556 KB
testcase_11	AC	899 ms 34,464 KB
testcase_12	AC	910 ms 25,632 KB
testcase_13	AC	1,078 ms 42,512 KB
testcase_14	AC	1,220 ms 47,024 KB
testcase_15	AC	1,053 ms 37,812 KB
testcase_16	AC	936 ms 25,704 KB
testcase_17	AC	979 ms 33,780 KB
testcase_18	AC	1,056 ms 34,796 KB
testcase_19	AC	1,095 ms 40,856 KB
testcase_20	AC	1,319 ms 47,864 KB
testcase_21	AC	1,317 ms 47,736 KB
testcase_22	AC	1,323 ms 47,736 KB
testcase_23	AC	1,265 ms 47,736 KB
testcase_24	AC	1,228 ms 47,608 KB
testcase_25	AC	1,213 ms 47,736 KB
testcase_26	AC	1,220 ms 47,608 KB
testcase_27	AC	1,245 ms 47,736 KB
testcase_28	AC	1,247 ms 47,736 KB
testcase_29	AC	1,232 ms 47,736 KB
testcase_30	AC	1,228 ms 47,736 KB
testcase_31	AC	1,253 ms 47,736 KB
testcase_32	AC	1,243 ms 47,608 KB
testcase_33	AC	1,248 ms 47,864 KB
testcase_34	AC	1,226 ms 47,736 KB
testcase_35	AC	1,221 ms 47,736 KB
testcase_36	AC	1,247 ms 47,608 KB
testcase_37	AC	1,237 ms 47,608 KB
testcase_38	AC	1,223 ms 47,736 KB
testcase_39	AC	1,231 ms 47,736 KB
testcase_40	AC	417 ms 53,472 KB
testcase_41	AC	380 ms 50,108 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In member function 'bool suisen::internal::kruscal::KruscalMST<CostType, ComparatorType>::build()':
main.cpp:80:28: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   80 |                 for (auto& [u, v, w] : _edges) {
      |                            ^
main.cpp: In lambda function:
main.cpp:138:33: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  138 |                     const auto &[xi, yi] = points[i];
      |                                 ^
main.cpp:139:33: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  139 |                     const auto &[xj, yj] = points[j];
      |                                 ^
main.cpp: In lambda function:
main.cpp:168:29: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  168 |                 const auto& [x, y] = points[i];
      |                             ^
main.cpp:170:21: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  170 |                 if (const auto p = pmq.prefix_max(cx + 1); p != pmq._neg_inf) {
      |                     ^~~~~
main.cpp:171:33: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  171 |                     const auto& [v, j] = p;
      |                                 ^
main.cpp: In function 'suisen::KruscalMinimumSpanningTree<WeightType> suisen::manhattan_mst(std::vector<std::pair<T, T> >)':
main.cpp:183:32: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  183 |                     for (auto& [x, y] : points) std::swap(x, y);
      |                                ^
main.cpp:185:28: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  185 |

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)
#define rep(i, n) drep(i, 0, n - 1)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;


template<typename T>
struct edge{
    int from, to;
    T cost;
    int id;

    edge(){}
    edge(int to, T cost=1) : from(-1), to(to), cost(cost){}
    edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}
    edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}
};

template<typename T>
struct redge{
    int from, to;
    T cap, cost;
    int rev;
    
    redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
    redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};

template<typename T> using Edges = vector<edge<T>>;
template<typename T> using weighted_graph = vector<Edges<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;

#include <atcoder/dsu>

namespace suisen {
    namespace internal::kruscal {
        // CostType: a type represents weights of edges i.e. (unsigned) int, (unsigned) long long, ...
        template <typename CostType, typename ComparatorType>
        struct KruscalMST {
            using cost_type = CostType;
            using edge_type = std::tuple<int, int, cost_type>;
            using comparator_type = ComparatorType;

            KruscalMST() : KruscalMST(0) {}
            explicit KruscalMST(const int n) : _n(n) {}

            void add_edge(const int u, const int v, const cost_type& cost) {
                _built = false;
                _edges.emplace_back(u, v, cost);
            }
            void add_edge(const edge_type& e) {
                _built = false;
                _edges.push_back(e);
            }
            /**
             * constructs the MST in O(ElogE) time using Kruskal's algprithm (E is the number of edges).
             * return: whether there exists MST or not (i.e. the graph is connected or not)
             */
            bool build() {
                _built = true;
                _weight_sum = 0;
                if (_n == 0) return true;
                atcoder::dsu uf(_n);
                std::sort(_edges.begin(), _edges.end(), [this](const auto& e1, const auto& e2) { return _comp(std::get<2>(e1), std::get<2>(e2)); });
                for (auto& [u, v, w] : _edges) {
                    if (uf.same(u, v)) {
                        u = v = _n;
                    } else {
                        uf.merge(u, v);
                        _weight_sum += w;
                    }
                }
                _edges.erase(std::remove_if(_edges.begin(), _edges.end(), [this](auto& e) { return std::get<0>(e) == _n; }), _edges.end());
                return int(_edges.size()) == _n - 1;
            }
            /**
             * ! This must not be called before calling `solve()`.
             * return:
             * 1. connected: sum of weights of edges in the minimum spanning tree
             * 2. otherwise: sum of weights of edges in the minimum spanning forest
             */
            cost_type get_weight() const {
                assert(_built);
                return _weight_sum;
            }
            /**
             * ! This must not be called before calling `solve()`.
             * return:
             * 1. connected: edges in the minimum spanning tree
             * 2. otherwise: edges in the minimum spanning forest
             * It is guaranteed that edges[i] <= edges[j] iff i <= j.
             */
            const std::vector<edge_type>& get_mst() const {
                assert(_built);
                return _edges;
            }
        private:
            int _n;
            cost_type _weight_sum;
            std::vector<edge_type> _edges;
            bool _built = false;
            comparator_type _comp{};
        };
    } // namespace internal::kruscal

    template <typename CostType>
    using KruscalMinimumSpanningTree = internal::kruscal::KruscalMST<CostType, std::less<CostType>>;
    template <typename CostType>
    using KruscalMaximumSpanningTree = internal::kruscal::KruscalMST<CostType, std::greater<CostType>>;
} // namespace suisen

namespace suisen {
    template <typename WeightType, typename T>
    KruscalMinimumSpanningTree<WeightType> manhattan_mst(std::vector<std::pair<T, T>> points) {
        const int n = points.size();
        std::vector<int> p(n);
        std::iota(p.begin(), p.end(), 0);

        auto make_edges = [&](KruscalMinimumSpanningTree<WeightType> &mst) {
            std::sort(
                p.begin(), p.end(),
                [&points](int i, int j) {
                    const auto &[xi, yi] = points[i];
                    const auto &[xj, yj] = points[j];
                    return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj;
                }
            );

            std::vector<T> comp_x(n);
            for (int i = 0; i < n; ++i) comp_x[i] = points[i].first;
            std::sort(comp_x.begin(), comp_x.end());
            comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end());
            const int m = comp_x.size();

            auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); };

            struct PrefixMaxQuery {
                const std::pair<T, int> _neg_inf{ std::numeric_limits<T>::min(), -1 };
                int _n;
                std::vector<std::pair<T, int>> _dat;
                PrefixMaxQuery(int n) : _n(n), _dat(_n + 1, _neg_inf) {}
                void chmax(int i, const std::pair<T, int>& val) {
                    for (++i; i <= _n; i += -i & i) if (_dat[i].first < val.first) _dat[i] = val;
                }
                std::pair<T, int> prefix_max(int r) const {
                    std::pair<T, int> res = _neg_inf;
                    for (; r; r -= -r & r) if (res.first < _dat[r].first) res = _dat[r];
                    return res;
                }
            } pmq{ m };

            for (int i : p) {
                const auto& [x, y] = points[i];
                const int cx = compress(x);
                if (const auto p = pmq.prefix_max(cx + 1); p != pmq._neg_inf) {
                    const auto& [v, j] = p;
                    mst.add_edge(i, j, x + y - v);
                }
                pmq.chmax(cx, { x + y, i });
            }
        };

        KruscalMinimumSpanningTree<WeightType> mst(n);
        for (int x_rev = 0; x_rev < 2; ++x_rev) {
            for (int y_rev = 0; y_rev < 2; ++y_rev) {
                for (int xy_rev = 0; xy_rev < 2; ++xy_rev) {
                    make_edges(mst);
                    for (auto& [x, y] : points) std::swap(x, y);
                }
                for (auto& [x, _] : points) x = -x;
            }
            for (auto& [_, y] : points) y = -y;
        }
        assert(mst.build());
        return mst;
    }
} // namespace suisen

void solve(){
    int n, l; cin >> n >> l;
    vector<pair<int, int>> points(n);
    for(int i=0; i<n; i++) cin >> points[i].fi >> points[i].se;

	auto mst = suisen::manhattan_mst<ll>(points);
	tree<int> T(n);
	for(auto [u, v, _] : mst.get_mst()){
		T[u].pb(edge<int>(v));
		T[v].pb(edge<int>(u));
	}

	vector<int> ans;
	function<void(int, int)> dfs = [&](int v, int p){
		ans.pb(v);
		for(edge<int> e : T[v]) if(e.to!=p) dfs(e.to, v);
	};
	dfs(0, -1);

	cout << n << '\n';
	for(int i=0; i<n; i++) cout << points[ans[i]].fi << " " << points[ans[i]].se << '\n';
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    cin >> T;
    while(T--) solve();
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード