oj.uz

답안 #375589

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375589 2021-03-09T14:54:15 Z muhi1112 Odašiljači (COCI20_odasiljaci) C++17
42 / 70
 120 ms 16852 KB 
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;

#define f1 first
#define s2 second
#define INF 1e9+10
#define ll long long
#define pb push_back
#define fri(a) freopen(a,"r",stdin)
#define fro(a) freopen(a,"w",stdout)
const int N=2e5+5;

int n,a,b,p[N];
vector<pair<int,int>>v;
vector<pair<long double,pair<int,int>>>u;
long double ans;

long double calc(pair<int,int>x,pair<int,int>y){
	return sqrt(abs((x.f1-y.f1)*(x.f1-y.f1))+abs((x.s2-y.s2)*(x.s2-y.s2)));
}

int parent(int x){
	if(x==p[x])return x;
	return p[x]=parent(p[x]);;
}

long double dsu(pair<long double,pair<int,int>> pp){
	int x=pp.s2.f1;
	int y=pp.s2.s2;
	x=parent(x);
	y=parent(y);
	if(x!=y){
		p[x]=y;
		return pp.f1;
	}
	else return 0.0;
}

void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		p[i]=i;
		cin>>a>>b;
		v.pb({a,b});
		for(int j=i-1;j>=0;j--){
			u.pb({calc(v[i],v[j]),{i,j}});
		}
	}
	sort(u.begin(),u.end());
	for(int i=0;i<u.size();i++){
		ans=max(ans,dsu(u[i]));
	}
	cout.precision(100);
	cout<<ans/2.0<<endl;


}

int main(){

	//fri("in.txt");
	//fro("out.txt");
	solve();

	return 0;
}

Compilation message

odasiljaci.cpp: In function 'void solve()':
odasiljaci.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~

Subtask #1
42.0 / 70.0

# 결과 실행 시간 메모리 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 Incorrect 1 ms 492 KB Output isn't correct
5 Incorrect 2 ms 748 KB Output isn't correct
6 Correct 32 ms 4572 KB Output is correct
7 Correct 35 ms 4572 KB Output is correct
8 Correct 92 ms 16852 KB Output is correct
9 Incorrect 119 ms 16852 KB Output isn't correct
10 Incorrect 120 ms 16852 KB Output isn't correct