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

提出ソース

結果

問題	No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
ユーザー	shobonvip
提出日時	2024-02-23 22:27:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	711 ms / 2,000 ms
コード長	3,947 bytes
コンパイル時間	5,370 ms
コンパイル使用メモリ	287,524 KB
実行使用メモリ	24,492 KB
最終ジャッジ日時	2024-02-23 22:28:46
合計ジャッジ時間	53,422 ms
ジャッジサーバーID （参考情報）	judge12 / judge16

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	366 ms 6,676 KB
testcase_02	AC	389 ms 6,676 KB
testcase_03	AC	397 ms 6,676 KB
testcase_04	AC	428 ms 6,676 KB
testcase_05	AC	417 ms 6,676 KB
testcase_06	AC	425 ms 6,676 KB
testcase_07	AC	501 ms 11,504 KB
testcase_08	AC	509 ms 10,712 KB
testcase_09	AC	496 ms 12,856 KB
testcase_10	AC	492 ms 12,560 KB
testcase_11	AC	486 ms 10,832 KB
testcase_12	AC	482 ms 12,532 KB
testcase_13	AC	542 ms 16,096 KB
testcase_14	AC	562 ms 20,716 KB
testcase_15	AC	529 ms 16,012 KB
testcase_16	AC	490 ms 12,148 KB
testcase_17	AC	513 ms 13,644 KB
testcase_18	AC	518 ms 14,096 KB
testcase_19	AC	513 ms 15,904 KB
testcase_20	AC	614 ms 21,308 KB
testcase_21	AC	659 ms 21,180 KB
testcase_22	AC	644 ms 21,180 KB
testcase_23	AC	608 ms 21,180 KB
testcase_24	AC	588 ms 21,180 KB
testcase_25	AC	630 ms 21,180 KB
testcase_26	AC	599 ms 21,180 KB
testcase_27	AC	602 ms 21,180 KB
testcase_28	AC	606 ms 21,180 KB
testcase_29	AC	611 ms 21,180 KB
testcase_30	AC	575 ms 21,180 KB
testcase_31	AC	607 ms 21,180 KB
testcase_32	AC	604 ms 21,180 KB
testcase_33	AC	711 ms 21,308 KB
testcase_34	AC	650 ms 21,180 KB
testcase_35	AC	706 ms 21,180 KB
testcase_36	AC	614 ms 21,180 KB
testcase_37	AC	610 ms 21,180 KB
testcase_38	AC	584 ms 21,180 KB
testcase_39	AC	575 ms 21,180 KB
testcase_40	AC	356 ms 24,480 KB
testcase_41	AC	411 ms 24,492 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

// https://judge.yosupo.jp/submission/117923
struct UnionFind {
    vector<int> par;
    vector<int> siz;
    vector<int> edg;

    UnionFind(int N) : par(N), siz(N), edg(N) {
        for(int i = 0; i < N; ++i){
            par[i] = i;
            siz[i] = 1;
            edg[i] = 0;
        }
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry){
            edg[rx]++;
            return;
        }
        par[rx] = ry;
        siz[ry] += siz[rx];
        edg[ry] += edg[rx] + 1;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return siz[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};
template <typename T>
vector<pair<int, int>> manhattanMST(vector<T> x, vector<T> y){
    int n = x.size();
    vector<tuple<T, int, int>> edge;
    edge.reserve(4 * n);
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    for(int s = 0; s < 2; ++s){
        for(int t = 0; t < 2; ++t){
            sort(idx.begin(), idx.end(), [&](const int i, const int j) {
                return x[i] + y[i] < x[j] + y[j];
            });
            map<T, int, greater<>> map;
            for(const int i : idx){
                for(auto iter = map.lower_bound(y[i]); iter != map.end(); iter = map.erase(iter)){
                    const int j = iter->second;
                    const T dx = x[i] - x[j];
                    const T dy = y[i] - y[j];
                    if(dy > dx) break;
                    edge.emplace_back(dx + dy, i, j);
                }
                map[y[i]] = i;
            }
            swap(x, y);
        }
        for(int i = 0; i < n; ++i) {
            x[i] *= -1;
        }
    }
    sort(edge.begin(), edge.end());
    UnionFind dsu(n);
    vector<pair<int, int>> used;
    used.reserve(n - 1);
    for(const auto& [c, i, j] : edge){
        if(!dsu.same(i, j)){
            used.emplace_back(i, j);
            dsu.unite(i, j);
        }
    }
    return used;
}
// -------

void solve(){
	int n;
	ll l; cin >> n >> l;
	vector<int> x(n), y(n);
	rep(i,0,n){
		cin >> x[i] >> y[i];
	}
	vector<pair<int,int>> mst = manhattanMST(x, y);
	
	vector ikeru(n, vector<int>(0));
	for (auto [i, j]: mst){
		ikeru[i].push_back(j);
		ikeru[j].push_back(i);
	}

	vector<int> ans;
	auto dfs = [&](auto self, int i, int p) -> void {
		ans.push_back(i);
		for (int j: ikeru[i]){
			if (j == p) continue;
			self(self, j, i);
			ans.push_back(i);
		}
	};

	dfs(dfs,0,-1);

	cout << (int)ans.size() << '\n';
	rep(i,0,(int)ans.size()){
		cout << x[ans[i]] << ' ' << y[ans[i]] << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t;
	cin >> t;
	while(t--) solve();
}

yukicoder

結果

テストケース

ソースコード