제출 #823816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823816		vjudge1	Sky Walking (IOI19_walk)	C++17	10 / 100	4051 ms	351948 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];


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();
	for(int i = 0; i < m; i++) {
		for(int building = l[i]; building <= r[i]; building++) {
			if(y[i] <= h[building]) in[building].push_back(y[i]);
		}
	}

	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++) {
		vector<int> ver;
		// cout << "seg: " << l[i] << ' ' << r[i] << ' ' << y[i] << '\n';
		for(int st = l[i]; st <= r[i]; st++) {
			if(h[st] >= y[i]) {
				ver.push_back(st);
				// cout << '[' << st << ' ' << find(in[st].begin(), in[st].end(), y[i]) - in[st].begin() << ']' << ' ';
			}
		}
		// cout << '\n';
		for(int z = 0; z < (int)ver.size() - 1; z++) {
			int st = ver[z], next = ver[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]});
		}
		// cout << '\n';
	}
	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: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43