Submission #601805

#	Time	Username	Problem	Language	Result	Execution time	Memory
601805		vanic	Roads (CEOI20_roads)	C++14	0 / 100	541 ms	524288 KiB

roads

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

struct union_find{
	int parent[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return parent[x]=find(parent[x]);
	}
	void update(int x, int y){
		if(rand()&1){
			swap(x, y);
		}
		parent[find(x)]=find(y);
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
};


union_find U;
pair < pair < int, int >, pair < int, int > > a[maxn];
vector < pair < ll, pair < int, int > > > v;

ll dist(pair < ll, ll > x, pair < ll, ll > y){
	return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i].first.first >> a[i].first.second >> a[i].second.first >> a[i].second.second;
	}
	ll d1, d2, d3, d4;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			d1=dist(a[i].first, a[j].first);
			d2=dist(a[i].second, a[j].first);
			d3=dist(a[i].first, a[j].second);
			d4=dist(a[i].second, a[j].second);
			if(d1<=d2 && d1<=d3 && d1<=d4){
				v.push_back({d1, {i*2, j*2}});
			}
			else if(d2<=d3 && d2<=d4){
				v.push_back({d2, {i*2+1, j*2}});
			}
			else if(d3<=d4){
				v.push_back({d3, {i*2, j*2+1}});
			}
			else{
				v.push_back({d4, {i*2+1, j*2+1}});
			}
		}
	}
	sort(v.begin(), v.end());
	
	for(int i=0; i<(int)v.size(); i++){
		if(!U.query(v[i].second.first/2, v[i].second.second/2)){
			if(v[i].second.first&1){
				cout << a[v[i].second.first/2].second.first << ' ' << a[v[i].second.first/2].second.second << ' ';
			}
			else{
				cout << a[v[i].second.first/2].first.first << ' ' << a[v[i].second.first/2].first.second << ' ';
			}
			if(v[i].second.second&1){
				cout << a[v[i].second.second/2].second.first << ' ' << a[v[i].second.second/2].second.second << '\n';
			}
			else{
				cout << a[v[i].second.second/2].first.first << ' ' << a[v[i].second.second/2].first.second << '\n';
			}
			U.update(v[i].second.first/2, v[i].second.second/2);
		}
	}
	return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40