結果

問題 No.168 ものさし
ユーザー mokomoko
提出日時 2018-03-16 13:30:47
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 2,490 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 167,684 KB
実行使用メモリ 11,508 KB
最終ジャッジ日時 2024-12-21 14:24:47
合計ジャッジ時間 3,573 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 29 ms
5,248 KB
testcase_12 AC 102 ms
11,508 KB
testcase_13 AC 143 ms
11,500 KB
testcase_14 AC 156 ms
11,376 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 3 ms
5,248 KB
testcase_17 AC 4 ms
5,248 KB
testcase_18 AC 10 ms
5,248 KB
testcase_19 AC 172 ms
11,508 KB
testcase_20 AC 162 ms
11,376 KB
testcase_21 AC 169 ms
11,504 KB
testcase_22 AC 168 ms
11,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,ll> P;
typedef pair<ll,P> PP;

//-----------------------------------------------------------------------------

template< typename T >
struct Kruskal {

	// Kruskalに必要なライブラリ開始。

	struct Edge {
		int from,to;
		T cost;

		Edge(int to,T cost):from(-1),to(to),cost(cost) {}
		Edge(int from,int to,T cost):from(from),to(to),cost(cost) {}

		bool operator<(const Edge &e) const {
			return cost<e.cost;
		}
	};

	using Edges=vector< Edge >;

	struct UnionFind {
		vector<int> data;
		UnionFind(int size):data(size,-1) {}
		bool unite(int x,int y) {
			x=root(x),y=root(y);
			if(x!=y) {
				if(data[y]<data[x]) swap(x,y);
				data[x]+=data[y],data[y]=x;
			}
			return x!=y;
		}
		bool same(int x,int y) {
			return root(x)==root(y);
		}
		int root(int x) {
			return data[x]<0?x:data[x]=root(data[x]);
		}
		int size(int x) {
			return -data[root(x)];
		}
	};

	// Kruskalに必要なライブラリ終了。

	int n;
	Edges edges;

	Kruskal() {}
	Kruskal(int _n):n(_n) {}

	void add_edge(int u,int v,T c) {
		edges.emplace_back(u,v,c);
	}

	void input(int m) {
		int a,b;T c;
		for(int i=0;i<m;i++) {
			cin>>a>>b>>c;
			add_edge(a,b,c);
		}
	}

	bool kruskal(ll mid) {
		//cout<<"mid "<<mid<<endl;
		UnionFind uf(n);
		//cout<<"after uf"<<endl;
		for(auto &e:edges) {
			if(!uf.same(e.from,e.to)&&e.cost<=mid*mid) {
				//cout<<"from="<<e.from<<",to="<<e.to<<endl;
				uf.unite(e.from,e.to);
			}
		}
		//for(int i=0;i<n;i++) cout<<uf.root(i)<<' ';
		//cout<<endl;
		return uf.same(0,n-1);
	}

	void show() {
		for(auto e:edges) cout<<'('<<e.from<<','<<e.to<<','<<e.cost<<')'<<endl;
	}

	void SORT() {
		sort(edges.begin(),edges.end());
	}
};

int n,x[1000],y[1000];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>n;
	REP(i,n) cin>>x[i]>>y[i];
	Kruskal<ll> G(n);
	REP(i,n) {
		FOR(j,i+1,n) {
			ll X=abs(x[i]-x[j]),Y=abs(y[i]-y[j]);
			G.add_edge(i,j,X*X+Y*Y);
		}
	}
	//G.show();
	G.SORT();
	ll ub=(ll)1e9,lb=0;
	while(ub-lb>1) {
		ll mid=(ub+lb)/2;
		if(G.kruskal(mid*10)) ub=mid;
		else lb=mid;
		//cout<<"ub,lb="<<ub<<' '<<lb<<endl;
	}
	cout<<ub*10<<endl;

	return 0;
}
0