제출 #427568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427568		amoo_safar	Sky Walking (IOI19_walk)	C++17	15 / 100	504 ms	33572 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 1e5 + 10;

int n, m;
vector<int> x, h, l, r, y;

int Get_Max(int l, int r){ // [l, r]
	// cerr << ""
	if(r < l) return -1;
	return h[l];
	int mx = h[l];
	for(int i = l; i <= r; i++)
		mx = max(mx, h[i]);
	return mx;
}
vector<pii> G[N];
void Add_Edge(int a, int b){
	// cerr << "!! " << a << ' ' << b << '\n';
	int ls = max(l[a], l[b]);
	int rs = min(r[a], r[b]);
	if(max(y[a], y[b]) <= Get_Max(ls, rs)){
		G[a].pb({b, abs(y[a] - y[b])});
		G[b].pb({a, abs(y[a] - y[b])});
	}
	// cerr << "!! " << a << ' ' << b << '\n';
}

vector<int> ins[N], dl[N];
void Add(vector<int> sg){
	for(int i = 0; i < N; i++) ins[i].clear(), dl[i].clear();
	for(int i : sg){
		ins[l[i]].pb(i);
		dl[r[i]].pb(i);
	}
	set< pair<int, int> > st; // y id

	for(int i = 0; i < N; i++){
		// cerr << "^^ " << i << '\n';	
		for(auto u : ins[i]){
			// cerr << "&& " << u << ' ' << y[u] << '\n';
			st.insert({y[u], u});
			auto it = st.find({y[u], u});
			if(it != st.begin())
				Add_Edge(it->S, prev(it) -> S);
			if(next(it) != st.end())
				Add_Edge(it->S, next(it) -> S);
		}
		// cerr << "^^ " << i << '\n';
		for(auto u : dl[i]){
			auto it = st.find({y[u], u});
			if(it != st.begin() && next(it) != st.end())
				Add_Edge(next(it) -> S, prev(it) -> S);
			st.erase(it);
		}
	}
}

ll dis[N];
typedef pair<ll, ll> pll;
ll Djik(int src, int des){
	memset(dis, 31, sizeof dis);
	dis[src] = 0;
	set<pll> st;
	st.insert({dis[src], src});
	while(!st.empty()){
		int fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto [adj, w] : G[fr]){
			if(dis[adj] > dis[fr] + w){
				st.erase({dis[adj], adj});
				dis[adj] = dis[fr] + w;
				st.insert({dis[adj], adj});
			}
		}
	}
	return dis[des];
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
	if(s > g) swap(s, g);
	x = _x;
	h = _h;

	ll ans = x[g] - x[s];
	
	_l.pb(s); _r.pb(s); _y.pb(0);
	_l.pb(g); _r.pb(g); _y.pb(0);
	
	int src = _l.size() - 2;
	int des = _r.size() - 1;

	n = _x.size();
	m = _l.size();
	
	l = _l;
	r = _r;
	y = _y;

	vector<int> lft, mid, rgt;
	for(int i = 0; i < m; i++) mid.pb(i);

	// debug("A");
	Add(lft);
	// debug("B");
	Add(mid);
	// debug("C");
	Add(rgt);
	// debug("D");

	ans += Djik(src, des);
	int max_len = 1000000000;
	return ans > 1ll * (n + m) * max_len ? -1 : ans;
}

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