oj.uz

Submission #376295

# Submission time Handle Problem Language Result Execution time Memory
376295 2021-03-11T07:44:02 Z errorgorn Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 94 ms 8672 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
ii arr[1005];
vector<ii> edges;

ll sq(ll i){
	return i*i;
}

ll dist(int i,int j){
	return sq(arr[i].fi-arr[j].fi)+sq(arr[i].se-arr[j].se);
}

struct UFDS{
	int p[1005];
	
	UFDS(){
		rep(x,0,1005) p[x]=x;
	}
	
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	
	bool unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return false;
		p[i]=j;
		return true;
	}
} ufds;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	
	rep(x,0,n){
		rep(y,x+1,n){
			edges.pub(ii(x,y));
		}
	}
	
	sort(all(edges),[](ii i,ii j){
		return dist(i.fi,i.se)<dist(j.fi,j.se);
	});
	
	ll ans=0;
	for (auto &it:edges){
		if (ufds.unions(it.fi,it.se)) ans=dist(it.fi,it.se);
	}
	
	cout<<fixed<<setprecision(12)<<sqrt(ans)/2<<endl;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 17 ms 2536 KB Output is correct
7 Correct 18 ms 2536 KB Output is correct
8 Correct 45 ms 8672 KB Output is correct
9 Correct 94 ms 8672 KB Output is correct
10 Correct 94 ms 8672 KB Output is correct