Submission #1267218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267218		dio_2	Roads (CEOI20_roads)	C++20	15 / 100	30 ms	7168 KiB

roads

#include<bits/stdc++.h>

int main(){
	using namespace std;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	vector<vector<int>> p(n, vector<int> (4));
	
	map<int, vector<vector<int>>> mapka;
	map<int, pair<int, int>> leader;
	vector<int> xs;
	int sub1 = 1; // all segments are vertical
	for(int i = 0;i < n;i++){
		for(int j = 0;j < 4;j++){
			cin >> p[i][j];
		}
		if(p[i][1] > p[i][3]){ // some order we have to give them.
			swap(p[i][1], p[i][3]);
			swap(p[i][0], p[i][2]);
		}
		sub1 &= (p[i][0] == p[i][2]); // x1 = x2
		mapka[p[i][0]].push_back(p[i]);
		if(leader.find(p[i][0]) == leader.end())
			xs.push_back(p[i][0]);
		leader[p[i][0]] = {p[i][0], p[i][1]};
	}
	
	vector<vector<int>> ans;
	auto add = [&](int a, int b, int c, int d) -> void {
		ans.push_back({a,b,c,d});
		return ;
	};
	sort(xs.begin(), xs.end());
	if(sub1){ // all vertical
		for(auto &[_,vec] : mapka){
			// we have all the pairs in this vertical line
			sort(vec.begin(), vec.end(), [&](const vector<int> v1, const vector<int> v2){
				return v1[1] < v2[1];
			});
			for(int i = 1;i < (int)vec.size();i++){
				add(vec[i-1][2], vec[i-1][3], vec[i][0], vec[i][1]);
			}
		}
		
		// now add the whole vertical lines themselves
		for(int i = 1;i < (int)xs.size();i++){
			add(leader[xs[i - 1]].first, leader[xs[i - 1]].second, leader[xs[i]].first, leader[xs[i]].second);
		}
		
		assert((int)ans.size() == n - 1);
		for(auto &vec : ans){
			for(int j = 0;j < 4;j++){
				cout << vec[j] << " \n"[j + 1 == 4];
			}
		}
		
		return 0;
	}
	
	return 0;
}

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