oj.uz

Submission #601805

# Submission time Handle Problem Language Result Execution time Memory
601805 2022-07-22T10:21:32 Z vanic Roads (CEOI20_roads) C++14
0 / 100
 541 ms 524288 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Runtime error 541 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 65 ms 9032 KB Output is correct
4 Runtime error 518 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 59 ms 9080 KB Output is correct
4 Runtime error 529 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 64 ms 9036 KB Output is correct
4 Runtime error 537 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 4 ms 1368 KB Output is correct
4 Correct 61 ms 9032 KB Output is correct
5 Runtime error 496 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Runtime error 505 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -