제출 #823823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823823		vjudge1	Sky Walking (IOI19_walk)	C++17	24 / 100	2611 ms	418068 KiB

walk

#include<bits/stdc++.h>
#include "walk.h"

using namespace std;
using ll = long long;
int n, m;

const int N = 1e5 + 10;
const int M = 2e6 + 10;
const ll INF = 1e15;

vector<pair<int, ll>> G[M];

vector<int> in[N];
int inx[N];

vector<int> cities[N];


long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = (int)x.size(), m = (int)y.size();
	// first = height, second = type, third = index
	vector<pair<int, pair<int, int>>> ord;	
	for(int i = 0; i < n; i++) 
		ord.push_back({h[i], {1, i}});
	for(int i = 0; i < m; i++) 
		ord.push_back({y[i], {0, i}});
	
	sort(ord.rbegin(), ord.rend());
	set<int> lux;
	for(auto cur : ord) {
		auto [type, inx] = cur.second;
		if(type) 
			lux.insert(inx);
		else {
			int x = l[inx] - 1;
			while(*(--lux.end()) > x) {
				x = *lux.upper_bound(x);
				if(x > r[inx]) break;
				in[x].push_back(y[inx]);
				cities[inx].push_back(x);
			}
			
		}
	}

	for(int i = 0; i < n; i++) {
		in[i].push_back(0);
		sort(in[i].begin(), in[i].end());
		if(i) inx[i] = inx[i - 1] + (int)in[i - 1].size();
		for(int r = 0; r < (int)in[i].size() - 1; r++) {
			G[inx[i] + r].push_back({inx[i] + r + 1, in[i][r + 1] - in[i][r]});
			G[inx[i] + r + 1].push_back({inx[i] + r, in[i][r + 1] - in[i][r]});
		}
	}
	// for(int i = 0; i < n; i++) {
	// 	cout << "cur: " << i << '\n';
	// 	cout << '[';
	// 	for(int t : in[i]) 
	// 		cout << t << " ";
	// 	cout << ']';
	// 	cout << '\n';
	// }
	for(int i = 0; i < m; i++) {
		for(int z = 0; z < (int)cities[i].size() - 1; z++) {
			int st = cities[i][z], next = cities[i][z + 1];
			int pos1 = find(in[st].begin(), in[st].end(), y[i]) - in[st].begin();
			int pos2 = find(in[next].begin(), in[next].end(), y[i]) - in[next].begin();
			G[inx[st] + pos1].push_back({inx[next] + pos2, x[next] - x[st]});
			G[inx[next] + pos2].push_back({inx[st] + pos1, x[next] - x[st]});
		}
	}
	int T = inx[n - 1] + (int)in[n - 1].size();

	vector<ll> dist(T, INF);
	dist[inx[g]] = 0;
	set<pair<ll, int>> st;
	for(int i = 0; i < T; i++) {
		st.insert({dist[i], i});
	}
	while(!st.empty()) {
		int s = st.begin()->second;
		st.erase(st.begin());
		for(auto [to, w] : G[s]) {
			if(dist[to] > dist[s] + w) {
				st.erase({dist[to], to});
				dist[to] = dist[s] + w;
				st.insert({dist[to], to});
			}
		}
	}
	int fin = inx[s];
	if(dist[fin] == INF) return -1;
	return dist[fin];
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43