oj.uz

Submission #667621

# Submission time Handle Problem Language Result Execution time Memory
667621 2022-12-01T19:56:33 Z dozer Roads (CEOI20_roads) C++14
30 / 100
 92 ms 15012 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define endl "\n"
#define sp " "
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int INF = 1e9 + 7;
const int modulo = 1e9 + 7;
int adj[N], x[N], y[N], done[N];

int32_t main()
{
	//fileio();
	fastio();

	int n;
	cin>>n;
	vector<int> vec;
	for (int i = 1; i <= n; i++)
	{
		int x1, x2, y1, y2;
		cin>>x1>>y1>>x2>>y2;
		int u = 2 * i - 1, v = 2 * i;
		x[u] = x1, y[u] = y1;
		x[v] = x2, y[v] = y2;

		adj[u] = v;
		adj[v] = u;

		vec.pb(u);
		vec.pb(v);
	}

	sort(vec.begin(), vec.end(), [&](int a, int b){
		return make_pair(y[a], x[a]) < make_pair(y[b], x[b]); 
	});
	//for (auto i : vec) cout<<i<<sp;
	//cout<<endl;
	vector<array<int, 4>> ans;
	set<pii> s;
	done[adj[vec.front()]] = 1;
	for (auto i : vec)
	{
		if (done[i] == 0 && !s.empty())
		{
			//cout<<i<<endl;
			auto it = s.lower_bound({x[i], -modulo});
			if (it == s.end()) it--;
			pii tmp = *it;
			ans.pb({x[i], y[i], tmp.st, -tmp.nd});
			done[i] = 1;
			done[adj[i]] = 1;
		}
		s.insert({x[i], -y[i]});
	}

	for (auto i : ans)
	{
		for (int j = 0; j < 4; j++) cout<<i[j]<<sp;
		cout<<endl;
	}

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Failed 73 ms 10484 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 14 ms 2912 KB Output is correct
5 Correct 30 ms 5620 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 14 ms 3024 KB Output is correct
5 Correct 33 ms 5664 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Failed 1 ms 340 KB Condition failed: "!Cross(S[*pi], S[*pa])"
8 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 15 ms 3024 KB Output is correct
5 Correct 31 ms 5576 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 15 ms 3280 KB Output is correct
10 Correct 92 ms 15012 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 15 ms 3248 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Failed 1 ms 340 KB Condition failed: "!Cross(S[*pi], S[*pa])"
8 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Failed 56 ms 10436 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -