oj.uz

Submission #833121

# Submission time Handle Problem Language Result Execution time Memory
833121 2023-08-22T01:35:08 Z 79brue Sky Walking (IOI19_walk) C++17
33 / 100
 879 ms 150276 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()){
				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()){
				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){
				//printf("Breaked because height[%d] = %d, towerIdx[%d][%d] = %d\n", i,height[i],i,j+1,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 30 ms 58964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 58964 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 149 ms 90144 KB Output is correct
2 Correct 449 ms 134956 KB Output is correct
3 Correct 582 ms 135764 KB Output is correct
4 Correct 688 ms 148520 KB Output is correct
5 Correct 852 ms 148536 KB Output is correct
6 Correct 713 ms 147688 KB Output is correct
7 Correct 367 ms 107840 KB Output is correct
8 Correct 282 ms 124324 KB Output is correct
9 Correct 735 ms 146244 KB Output is correct
10 Correct 340 ms 124220 KB Output is correct
11 Correct 41 ms 63052 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 90144 KB Output is correct
2 Correct 449 ms 134956 KB Output is correct
3 Correct 582 ms 135764 KB Output is correct
4 Correct 688 ms 148520 KB Output is correct
5 Correct 852 ms 148536 KB Output is correct
6 Correct 713 ms 147688 KB Output is correct
7 Correct 367 ms 107840 KB Output is correct
8 Correct 282 ms 124324 KB Output is correct
9 Correct 735 ms 146244 KB Output is correct
10 Correct 340 ms 124220 KB Output is correct
11 Correct 41 ms 63052 KB Output is correct
12 Correct 560 ms 136248 KB Output is correct
13 Correct 389 ms 145828 KB Output is correct
14 Correct 772 ms 148976 KB Output is correct
15 Correct 522 ms 131068 KB Output is correct
16 Correct 601 ms 138748 KB Output is correct
17 Correct 694 ms 144708 KB Output is correct
18 Correct 550 ms 131000 KB Output is correct
19 Correct 638 ms 138976 KB Output is correct
20 Correct 366 ms 108412 KB Output is correct
21 Correct 61 ms 67456 KB Output is correct
22 Correct 280 ms 128744 KB Output is correct
23 Correct 269 ms 127508 KB Output is correct
24 Correct 252 ms 118684 KB Output is correct
25 Correct 267 ms 123964 KB Output is correct
26 Correct 210 ms 114312 KB Output is correct
27 Correct 879 ms 150276 KB Output is correct
28 Correct 364 ms 144536 KB Output is correct
29 Correct 710 ms 146692 KB Output is correct
30 Correct 389 ms 108132 KB Output is correct
31 Correct 676 ms 146744 KB Output is correct
32 Correct 301 ms 125332 KB Output is correct
33 Correct 304 ms 128540 KB Output is correct
34 Correct 363 ms 135240 KB Output is correct
35 Correct 361 ms 132616 KB Output is correct
36 Correct 324 ms 126000 KB Output is correct
37 Correct 284 ms 126396 KB Output is correct
38 Correct 260 ms 130236 KB Output is correct
39 Correct 401 ms 140880 KB Output is correct
40 Correct 310 ms 128936 KB Output is correct
41 Correct 296 ms 124760 KB Output is correct

Subtask #5
0 / 43.0

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