Submission #298326

#	Time	Username	Problem	Language	Result	Execution time	Memory
298326		amoo_safar	Sky Walking (IOI19_walk)	C++17	0 / 100	395 ms	26636 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()
using namespace std;

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


const int N = 1e5 + 10;
const ll Inf = 1e18;

vector< pair<int, int> > G[N];
vector<int> x, h, l, r, y;
int n, m;

void AddEdge(int u, int v){
	//cerr << "# " << u << ' ' << v << '\n';
	int w = abs(y[u] - y[v]);
	G[u].pb({v, w});
	G[v].pb({u, w});
}

set<pii> st;

void Add(int id){
	st.insert({y[id], id});
	auto it = st.find({y[id], id});
	if(it != st.begin())
		AddEdge(id, prev(it) -> S);
	if(next(it) != st.end())
		AddEdge(id, next(it) -> S);
}
void Rem(int id){
	st.erase({y[id], id});
}
vector<int> evA[N], evR[N];

ll dis[N];
set< pli > pq;

ll Djik(){
	memset(dis, 31, sizeof dis);
	for(int i = 0; i < m; i++){
		if(l[i] == 0){
			dis[i] = y[i];
			pq.insert({dis[i], i});
		}
	}
	int fr;
	while(!pq.empty()){
		fr = pq.begin() -> S;
		//cerr << fr << ' ' << dis[fr] << '\n';
		pq.erase(pq.begin());

		for(auto [adj, w] : G[fr]){
			if(dis[adj] > dis[fr] + w){
				pq.erase({dis[adj], adj});
				dis[adj] = dis[fr] + w;
				pq.insert({dis[adj], adj});
			}
		}
	}
	ll res = Inf;
	for(int i = 0; i < m; i++){
		if(r[i] == n - 1)
			res = min(res, dis[i] + y[i]);
	}
	return res == Inf ? -1 : res;
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
	
	x = _x; h = _h; l = _l; r = _r; y = _y;
	n = x.size(); m = y.size();
	assert(s == 0 && g == n - 1);
	
	ll ans = x[g] - x[s];

	for(int i = 0; i < m; i++){
		evA[l[i]].pb(i);
		evR[r[i] + 1].pb(i);
	}
	for(int i = 0; i < n; i++){
		for(auto x : evA[i]) Add(x);
		for(auto x : evR[i]) Rem(x);
	}
	ll dij = Djik();
	return dij == -1 ? -1 : dij + ans;
}

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