oj.uz

Submission #833116

# Submission time Handle Problem Language Result Execution time Memory
833116 2023-08-22T01:19:07 Z 79brue Sky Walking (IOI19_walk) C++17
33 / 100
 788 ms 140656 KB 
#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
	int l, r, y, idx;
	Edge(){}
	Edge(int l, int r, int y, int idx): l(l), r(r), y(y), idx(idx){}
	bool operator<(const Edge &r)const{
		if(y != r.y) return y < r.y;
		return idx < r.idx;
	}
};

int n, k, Start, Goal;
ll arr[100002];
ll height[100002];
ll el[100002], er[100002], ey[100002];

void findIntersections();
ll solve();

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r,
			    vector<int> _y, int _s, int _t) {
	n = (int)_x.size();
	for(int i=1; i<=n; i++) arr[i] = _x[i-1], height[i] = _h[i-1];
	k = (int)_l.size();

	vector<Edge> vec;
	for(int i=1; i<=k; i++) vec.push_back(Edge(_l[i-1] + 1, _r[i-1] + 1, _y[i-1], i));
	sort(vec.begin(), vec.end());
	
	for(int i=1; i<=k; i++) el[i] = vec[i-1].l, er[i] = vec[i-1].r, ey[i] = vec[i-1].y;
	
	Start = _s+1, Goal = _t+1;

	findIntersections();
	return solve();
}

/// 정점과 간선 정보
int floorV[100002];
vector<pair<int, ll> > link[2000002];
vector<int> addLine[100002], delLine[100002];

vector<pair<int, int> > edgeIdx[100002]; /// 간선별로 정점을 추가할 x좌표들, 그리고 그 정점 번호
vector<pair<int, int> > towerIdx[100002]; /// x좌표별로 정점을 추가할 높이들, 그리고 그 정점 번호
int recent[100002];

vector<int> insertionPoint[100002];

void findIntersections(){
	for(int i=1; i<=k; i++){
		addLine[el[i]].push_back(i);
		delLine[er[i]].push_back(i);
	}

	/// Subtask 4의 정점들만 추가
	int vCnt = 0;
	set<int> st; /// 간선 번호
	for(int i=1; i<=n; i++){
		for(int x: addLine[i]){
			// printf("addLine %d - %d\n", i, x);
			edgeIdx[x].push_back(make_pair(arr[i], ++vCnt));
			towerIdx[i].push_back(make_pair(ey[x], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[x]);
			recent[x] = i;

			auto it = st.insert(x).first;
			if(it != st.begin() && recent[*prev(it)] != i){
				int y = *prev(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
			if(next(it) != st.end() && recent[*next(it)] != i){
				int y = *next(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
		}
		for(int x: delLine[i]){
			// printf("delLine %d - %d\n", i, x);
			edgeIdx[x].push_back(make_pair(arr[i], ++vCnt));
			towerIdx[i].push_back(make_pair(ey[x], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[x]);
			recent[x] = i;

			auto it = st.find(x);
			if(it != st.begin() && recent[*prev(it)] != i && arr[*prev(it)] <= ey[i]){
				int y = *prev(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
			if(next(it) != st.end() && recent[*next(it)] != i && arr[*next(it)] <= ey[i]){
				int y = *next(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
			st.erase(x);
		}
		towerIdx[i].push_back(make_pair(0, ++vCnt));
		floorV[i] = vCnt;
		// printf("%d: (%d, %d)\n", vCnt, arr[i], 0);
	}

	/// Full task의 정점들도 추가
	st.clear();
	for(int i=1; i<=n; i++){
		auto it = prev(upper_bound(ey+1, ey+k+1, height[i]));
		if(it == ey) continue;
		insertionPoint[it-ey].push_back(i);
		// printf("%d: bound %d (height[i] %d)\n", i, it-ey, height[i]);
	}
	/*for(int i=k; i>=1; i--){
		for(int x: insertionPoint[i]){
			// printf("Inserted %d in %d\n", x, i);
			st.insert(x);
		}

		auto it = st.lower_bound(Start);
		if(it != st.end() && el[i] <= *it && *it <= er[i]){
			int x = *it;
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}
		if(it != st.begin() && el[i] <= *prev(it) && *prev(it) <= er[i]){
			int x = *prev(it);
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}

		it = st.lower_bound(Goal);
		if(it != st.end() && el[i] <= *it && *it <= er[i]){
			int x = *it;
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}
		if(it != st.begin() && el[i] <= *prev(it) && *prev(it) <= er[i]){
			int x = *prev(it);
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}
	}*/

	/// 정점들을 간선으로 연결
	for(int i=1; i<=k; i++){
		sort(edgeIdx[i].begin(), edgeIdx[i].end());
		for(int j=0; j<(int)edgeIdx[i].size()-1; j++){
			int x = edgeIdx[i][j].second, y = edgeIdx[i][j+1].second;
			int v = edgeIdx[i][j+1].first - edgeIdx[i][j].first;
			// printf("Connect %d %d : %d\n", x, y, v);
			link[x].push_back(make_pair(y, v));
			link[y].push_back(make_pair(x, v));
		}
	}

	for(int i=1; i<=n; i++){
		sort(towerIdx[i].begin(), towerIdx[i].end());
		for(int j=0; j<(int)towerIdx[i].size()-1; j++){
			// printf("i %d j %d arr[i] %d towerIdx[i][j+1].first %d\n", i, j, height[i], towerIdx[i][j+1].first);
			//if(height[i] < towerIdx[i][j+1].first) break;
			int x = towerIdx[i][j].second, y = towerIdx[i][j+1].second;
			int v = towerIdx[i][j+1].first - towerIdx[i][j].first;
			// printf("Connect %d %d : %d\n", x, y, v);
			link[x].push_back(make_pair(y, v));
			link[y].push_back(make_pair(x, v));
		}
	}
	assert(vCnt <= 2000000);
}

struct dat{
	int x; ll d;
	dat(){}
	dat(int x, ll d): x(x), d(d){}
	bool operator<(const dat &r)const{
		return d>r.d;
	}
};
bool visited[2000002];

ll solve(){
	// printf("Solve %d to %d\n", floorV[Start], floorV[Goal]);
	priority_queue<dat> pq;
	pq.push(dat(floorV[Start], 0));
	while(!pq.empty()){
		dat tmp = pq.top(); pq.pop();
		if(visited[tmp.x]) continue;
		// printf("%d: %lld\n", tmp.x, tmp.d);
		if(tmp.x == floorV[Goal]) return tmp.d;
		visited[tmp.x] = 1;

		for(pair<int, ll> p: link[tmp.x]){
			pq.push(dat(p.first, tmp.d + p.second));
		}
	}
	// // printf("No solution\n");
	return -1;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 58984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 58956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 81480 KB Output is correct
2 Correct 462 ms 133188 KB Output is correct
3 Correct 563 ms 133196 KB Output is correct
4 Correct 568 ms 133368 KB Output is correct
5 Correct 788 ms 140656 KB Output is correct
6 Correct 609 ms 140124 KB Output is correct
7 Correct 293 ms 99416 KB Output is correct
8 Correct 237 ms 112164 KB Output is correct
9 Correct 648 ms 133632 KB Output is correct
10 Correct 289 ms 115860 KB Output is correct
11 Correct 38 ms 62760 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 81480 KB Output is correct
2 Correct 462 ms 133188 KB Output is correct
3 Correct 563 ms 133196 KB Output is correct
4 Correct 568 ms 133368 KB Output is correct
5 Correct 788 ms 140656 KB Output is correct
6 Correct 609 ms 140124 KB Output is correct
7 Correct 293 ms 99416 KB Output is correct
8 Correct 237 ms 112164 KB Output is correct
9 Correct 648 ms 133632 KB Output is correct
10 Correct 289 ms 115860 KB Output is correct
11 Correct 38 ms 62760 KB Output is correct
12 Correct 541 ms 133500 KB Output is correct
13 Correct 339 ms 127492 KB Output is correct
14 Correct 675 ms 135032 KB Output is correct
15 Correct 483 ms 125492 KB Output is correct
16 Correct 528 ms 125648 KB Output is correct
17 Correct 615 ms 132168 KB Output is correct
18 Correct 498 ms 125448 KB Output is correct
19 Correct 526 ms 125676 KB Output is correct
20 Correct 277 ms 98856 KB Output is correct
21 Correct 56 ms 66984 KB Output is correct
22 Correct 475 ms 117868 KB Output is correct
23 Correct 458 ms 116924 KB Output is correct
24 Correct 428 ms 113672 KB Output is correct
25 Correct 418 ms 114160 KB Output is correct
26 Correct 402 ms 118804 KB Output is correct
27 Correct 678 ms 135832 KB Output is correct
28 Correct 337 ms 127788 KB Output is correct
29 Correct 607 ms 132108 KB Output is correct
30 Correct 289 ms 98936 KB Output is correct
31 Correct 603 ms 134632 KB Output is correct
32 Correct 252 ms 112956 KB Output is correct
33 Correct 327 ms 119704 KB Output is correct
34 Correct 333 ms 121876 KB Output is correct
35 Correct 340 ms 124016 KB Output is correct
36 Correct 287 ms 118432 KB Output is correct
37 Correct 239 ms 114812 KB Output is correct
38 Correct 352 ms 128552 KB Output is correct
39 Correct 355 ms 138340 KB Output is correct
40 Correct 310 ms 126604 KB Output is correct
41 Correct 258 ms 117396 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 58984 KB Output isn't correct
2 Halted 0 ms 0 KB -