oj.uz

Submission #425148

# Submission time Handle Problem Language Result Execution time Memory
425148 2021-06-12T14:01:00 Z donentseto Sky Walking (IOI19_walk) C++14
24 / 100
 1125 ms 150384 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
int n, m, nodes;
struct building{
	int x, h;
	bool operator < (building oth) const{
		return x < oth.x;
	}
};
bool comp (building a, building b){
	return a.h < b.h;
}
struct skywalk{
	int l, r, y;
	bool operator < (skywalk oth) const{
		return y < oth.y;
	}
};
vector <building> b;
set <building> s;
vector <skywalk> w;
vector <pair <int, int> > intersect [maxn];
vector <pair <int, int> > adj [maxn * 10];
bool used [maxn * 10];

long long dejkstra (int a, int A){

	priority_queue <pair <long long, int> > pq;
	pq.push ({0, a});
	while (!pq.empty ()){
		auto p = pq.top ();
		pq.pop ();
		if (used [p.second]) continue;
		if (p.second == A) return -p.first;
		used [p.second] = 1;
		for (auto e : adj [p.second]){
			if (used [e.first]) continue;
			pq.push ({p.first - e.second, e.first});
		}
	}

	return -1;

}

long long min_distance (vector <int> x, vector <int> h, vector <int> l, vector <int> r, vector <int> y, int start, int end){

	n = x.size ();
	m = l.size ();
	for (int i = 0; i < n; i ++){
		b.push_back ({i, h [i]});
	}
	for (int i = 0; i < m; i ++){
		w.push_back ({l [i], r [i], y [i]});
	}
	sort (b.begin (), b.end (), comp);
	sort (w.begin (), w.end ());

	int idx = n - 1;
	for (int i = m - 1; i >= 0; i --){
		while (idx >= 0 && b [idx].h >= w [i].y){
			s.insert (b [idx]);
			idx --;
		}
		building b = {w [i].l, 0};
		auto it = s.lower_bound (b);
		vector <int> v;
		while ((*it).x != w [i].r){
			v.push_back ((*it).x);
			++it;
		}
		v.push_back (w [i].r);
		int sz = v.size ();
		intersect [v [0]].push_back ({w [i].y, nodes ++});
		for (int j = 1; j < sz; j ++){
			adj [nodes - 1].push_back ({nodes, x [v [j]] - x [v [j - 1]]});
			adj [nodes].push_back ({nodes - 1, x [v [j]] - x [v [j - 1]]});
			intersect [v [j]].push_back ({w [i].y, nodes ++});
		}
	}
	intersect [start].push_back ({0, nodes ++});
	intersect [end].push_back ({0, nodes ++});
	for (int i = 0; i < n; i ++){
		int sz = intersect [i].size ();
		for (int j = 1; j < sz; j ++){
			adj [intersect [i][j].second].push_back ({intersect [i][j - 1].second, intersect [i][j - 1].first - intersect [i][j].first});
			adj [intersect [i][j - 1].second].push_back ({intersect [i][j].second, intersect [i][j - 1].first - intersect [i][j].first});
		}
	}

	return dejkstra (nodes - 2, nodes - 1);

}
/*
int main (){

	cout << min_distance({0, 3, 5, 7, 10, 12, 14},
			{8, 7, 9, 7, 6, 6, 9},
			{0, 0, 0, 2, 2, 3, 4},
			{1, 2, 6, 3, 6, 4, 6},
			{1, 6, 8, 1, 7, 2, 5},
			1, 5) << '\n';

}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26036 KB Output is correct
2 Correct 17 ms 26132 KB Output is correct
3 Correct 15 ms 26132 KB Output is correct
4 Correct 14 ms 26132 KB Output is correct
5 Correct 19 ms 26104 KB Output is correct
6 Correct 15 ms 26168 KB Output is correct
7 Correct 14 ms 26160 KB Output is correct
8 Correct 16 ms 26116 KB Output is correct
9 Correct 14 ms 26060 KB Output is correct
10 Correct 17 ms 26136 KB Output is correct
11 Correct 14 ms 26060 KB Output is correct
12 Correct 14 ms 26060 KB Output is correct
13 Correct 14 ms 26112 KB Output is correct
14 Correct 14 ms 26128 KB Output is correct
15 Correct 18 ms 26036 KB Output is correct
16 Correct 18 ms 26060 KB Output is correct
17 Correct 16 ms 26188 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26112 KB Output is correct
2 Correct 17 ms 26136 KB Output is correct
3 Correct 449 ms 76292 KB Output is correct
4 Correct 883 ms 85840 KB Output is correct
5 Correct 541 ms 76552 KB Output is correct
6 Correct 457 ms 71712 KB Output is correct
7 Correct 525 ms 76716 KB Output is correct
8 Correct 580 ms 88808 KB Output is correct
9 Correct 590 ms 76504 KB Output is correct
10 Correct 1125 ms 102924 KB Output is correct
11 Correct 379 ms 57760 KB Output is correct
12 Correct 307 ms 48808 KB Output is correct
13 Correct 1010 ms 96436 KB Output is correct
14 Correct 247 ms 50268 KB Output is correct
15 Correct 260 ms 49508 KB Output is correct
16 Correct 277 ms 50132 KB Output is correct
17 Correct 256 ms 49844 KB Output is correct
18 Correct 166 ms 49192 KB Output is correct
19 Correct 24 ms 27156 KB Output is correct
20 Correct 112 ms 37604 KB Output is correct
21 Correct 245 ms 48528 KB Output is correct
22 Correct 228 ms 49376 KB Output is correct
23 Correct 247 ms 56724 KB Output is correct
24 Correct 236 ms 49876 KB Output is correct
25 Correct 249 ms 50124 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36348 KB Output is correct
2 Runtime error 258 ms 150384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36348 KB Output is correct
2 Runtime error 258 ms 150384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26036 KB Output is correct
2 Correct 17 ms 26132 KB Output is correct
3 Correct 15 ms 26132 KB Output is correct
4 Correct 14 ms 26132 KB Output is correct
5 Correct 19 ms 26104 KB Output is correct
6 Correct 15 ms 26168 KB Output is correct
7 Correct 14 ms 26160 KB Output is correct
8 Correct 16 ms 26116 KB Output is correct
9 Correct 14 ms 26060 KB Output is correct
10 Correct 17 ms 26136 KB Output is correct
11 Correct 14 ms 26060 KB Output is correct
12 Correct 14 ms 26060 KB Output is correct
13 Correct 14 ms 26112 KB Output is correct
14 Correct 14 ms 26128 KB Output is correct
15 Correct 18 ms 26036 KB Output is correct
16 Correct 18 ms 26060 KB Output is correct
17 Correct 16 ms 26188 KB Output is correct
18 Correct 17 ms 26112 KB Output is correct
19 Correct 17 ms 26136 KB Output is correct
20 Correct 449 ms 76292 KB Output is correct
21 Correct 883 ms 85840 KB Output is correct
22 Correct 541 ms 76552 KB Output is correct
23 Correct 457 ms 71712 KB Output is correct
24 Correct 525 ms 76716 KB Output is correct
25 Correct 580 ms 88808 KB Output is correct
26 Correct 590 ms 76504 KB Output is correct
27 Correct 1125 ms 102924 KB Output is correct
28 Correct 379 ms 57760 KB Output is correct
29 Correct 307 ms 48808 KB Output is correct
30 Correct 1010 ms 96436 KB Output is correct
31 Correct 247 ms 50268 KB Output is correct
32 Correct 260 ms 49508 KB Output is correct
33 Correct 277 ms 50132 KB Output is correct
34 Correct 256 ms 49844 KB Output is correct
35 Correct 166 ms 49192 KB Output is correct
36 Correct 24 ms 27156 KB Output is correct
37 Correct 112 ms 37604 KB Output is correct
38 Correct 245 ms 48528 KB Output is correct
39 Correct 228 ms 49376 KB Output is correct
40 Correct 247 ms 56724 KB Output is correct
41 Correct 236 ms 49876 KB Output is correct
42 Correct 249 ms 50124 KB Output is correct
43 Correct 124 ms 36348 KB Output is correct
44 Runtime error 258 ms 150384 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -