結果
問題 | No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ |
ユーザー | Misuki |
提出日時 | 2024-02-23 22:41:41 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 980 ms / 2,000 ms |
コード長 | 4,304 bytes |
コンパイル時間 | 4,413 ms |
コンパイル使用メモリ | 228,356 KB |
実行使用メモリ | 63,904 KB |
最終ジャッジ日時 | 2024-02-23 22:42:53 |
合計ジャッジ時間 | 64,671 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 387 ms
6,548 KB |
testcase_02 | AC | 378 ms
6,548 KB |
testcase_03 | AC | 389 ms
6,548 KB |
testcase_04 | AC | 466 ms
6,548 KB |
testcase_05 | AC | 467 ms
6,676 KB |
testcase_06 | AC | 470 ms
6,548 KB |
testcase_07 | AC | 632 ms
27,436 KB |
testcase_08 | AC | 615 ms
24,964 KB |
testcase_09 | AC | 682 ms
32,804 KB |
testcase_10 | AC | 666 ms
29,772 KB |
testcase_11 | AC | 625 ms
28,296 KB |
testcase_12 | AC | 644 ms
29,896 KB |
testcase_13 | AC | 767 ms
41,484 KB |
testcase_14 | AC | 939 ms
53,884 KB |
testcase_15 | AC | 770 ms
34,832 KB |
testcase_16 | AC | 652 ms
28,704 KB |
testcase_17 | AC | 729 ms
31,700 KB |
testcase_18 | AC | 788 ms
33,424 KB |
testcase_19 | AC | 747 ms
41,796 KB |
testcase_20 | AC | 961 ms
56,644 KB |
testcase_21 | AC | 971 ms
56,360 KB |
testcase_22 | AC | 975 ms
56,336 KB |
testcase_23 | AC | 928 ms
56,396 KB |
testcase_24 | AC | 935 ms
56,216 KB |
testcase_25 | AC | 980 ms
56,456 KB |
testcase_26 | AC | 953 ms
56,308 KB |
testcase_27 | AC | 949 ms
56,400 KB |
testcase_28 | AC | 970 ms
56,348 KB |
testcase_29 | AC | 935 ms
56,348 KB |
testcase_30 | AC | 922 ms
56,448 KB |
testcase_31 | AC | 914 ms
56,484 KB |
testcase_32 | AC | 910 ms
56,184 KB |
testcase_33 | AC | 952 ms
56,628 KB |
testcase_34 | AC | 970 ms
56,424 KB |
testcase_35 | AC | 963 ms
56,464 KB |
testcase_36 | AC | 960 ms
56,188 KB |
testcase_37 | AC | 903 ms
56,260 KB |
testcase_38 | AC | 912 ms
56,340 KB |
testcase_39 | AC | 931 ms
56,392 KB |
testcase_40 | AC | 416 ms
63,904 KB |
testcase_41 | AC | 382 ms
63,736 KB |
ソースコード
#pragma GCC optimize("O2") #include <algorithm> #include <array> #include <bit> #include <bitset> #include <cassert> #include <cctype> #include <cfenv> #include <cfloat> #include <chrono> #include <cinttypes> #include <climits> #include <cmath> #include <compare> #include <complex> #include <concepts> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <initializer_list> #include <iomanip> #include <ios> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <new> #include <numbers> #include <numeric> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <span> #include <sstream> #include <stack> #include <streambuf> #include <string> #include <tuple> #include <type_traits> #include <variant> #define int ll #define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1) #define INT128_MIN (-INT128_MAX - 1) #define clock chrono::steady_clock::now().time_since_epoch().count() #ifdef DEBUG #define dbg(x) cout << (#x) << " = " << x << '\n' #else #define dbg(x) #endif namespace R = std::ranges; namespace V = std::views; using namespace std; using ll = long long; using ull = unsigned long long; using ldb = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; //#define double ldb template<class T> ostream& operator<<(ostream& os, const pair<T, T> pr) { return os << pr.first << ' ' << pr.second; } template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N> &arr) { for(const T &X : arr) os << X << ' '; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T> &vec) { for(const T &X : vec) os << X << ' '; return os; } template<class T> ostream& operator<<(ostream& os, const set<T> &s) { for(const T &x : s) os << x << ' '; return os; } using lld = int64_t; class DSU { vector<int> v; public: DSU(int n): v(n) { iota(v.begin(), v.end(), 0); } int query(int u) { return v[u] == u ? u : v[u] = query(v[u]); } void merge(int x, int y) { v[query(x)] = query(y); } }; template <typename T> struct Point { T x, y; Point(T x_ = 0, T y_ = 0): x(x_), y(y_) {} Point operator-(const Point &rhs) const { return Point(x - rhs.x, y - rhs.y); } }; typedef Point<int> P; vector<tuple<int, int, int>> manhattanMST(vector<P> ps) { vector<int> id(ps.size()); iota(id.begin(), id.end(), 0); vector<tuple<int, int, int>> edges; for (int k = 0; k < 4; ++k) { sort(id.begin(), id.end(), [&](int i, int j) { return (ps[i] - ps[j]).x < (ps[j] - ps[i]).y; }); map<int, int> sweep; for (int i : id) { for (auto it = sweep.lower_bound(-ps[i].y); it != sweep.end(); sweep.erase(it++)) { int j = it->second; P d = ps[i] - ps[j]; if (d.y > d.x) break; edges.emplace_back(d.y + d.x, i, j); } sweep[-ps[i].y] = i; } for (P &p : ps) if (k & 1) p.x = -p.x; else swap(p.x, p.y); } return edges; } vector<int> MST(int n, const vector<tuple<int, int, int>> &e) { vector<int> idx(e.size()); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j){ return get<0>(e[i]) < get<0>(e[j]); }); vector<int> r; DSU dsu(n); for (int o: idx) { const auto &[w, i, j] = e[o]; if (dsu.query(i) == dsu.query(j)) continue; r.push_back(o); dsu.merge(i, j); } return r; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while(t--) { int n, l; cin >> n >> l; vector<P> ps(n); for(auto &[x, y] : ps) cin >> x >> y; auto e = manhattanMST(ps); auto r = MST(n, e); vector<vector<int>> g(n); for(auto i : r) { auto [_, u, v] = e[i]; g[u].emplace_back(v); g[v].emplace_back(u); } vector<P> ans; auto dfs = [&](int v, int p, auto self) -> void { ans.emplace_back(ps[v]); for(int x : g[v]) { if (x == p) continue; self(x, v, self); ans.emplace_back(ps[v]); } }; dfs(0, -1, dfs); cout << ssize(ans) << '\n'; for(auto [x, y] : ans) cout << x << ' ' << y << '\n'; } return 0; }