結果
| 問題 |
No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
|
| コンテスト | |
| ユーザー |
 umimel
|
| 提出日時 | 2024-02-23 23:16:41 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,318 ms / 2,000 ms |
| コード長 | 8,100 bytes |
| コンパイル時間 | 2,647 ms |
| コンパイル使用メモリ | 199,792 KB |
| 実行使用メモリ | 52,584 KB |
| 最終ジャッジ日時 | 2024-09-29 08:45:32 |
| 合計ジャッジ時間 | 64,373 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 42 |
コンパイルメッセージ
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 |
ソースコード
#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();
}