Submission #1318456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318456		PlayVoltz	Sky Walking (IOI19_walk)	C++20	33 / 100	545 ms	93872 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed start, signed end){
	vector<vector<pii> > graph(max(y.size(), x.size())*10), vect(x.size());
	vector<pii> ooga(h.size()), booga(y.size());
	for (int i=0; i<h.size(); ++i)ooga[i]=mp(h[i], i);
	for (int i=0; i<y.size(); ++i)booga[i]=mp(y[i], i);
	sort(ooga.begin(), ooga.end(), greater<pii>());
	sort(booga.begin(), booga.end(), greater<pii>());
	set<int> s;
	int p=0, counter=0;
	for (auto c:booga){
		if (r[c.se]<=start||start<=l[c.se])continue;
		while (p<h.size()&&ooga[p].fi>=c.fi)s.insert(ooga[p].se), ++p;
		int a=*(--s.upper_bound(start)), b=*s.lower_bound(start);
		l.pb(l[c.se]), r.pb(a), y.pb(c.fi);
		l.pb(a), r.pb(b), y.pb(c.fi);
		l.pb(b), r.pb(r[c.se]), y.pb(c.fi);
		a=*(--s.upper_bound(end)), b=*s.lower_bound(end);
		l.pb(l[c.se]), r.pb(a), y.pb(c.fi);
		l.pb(a), r.pb(b), y.pb(c.fi);
		l.pb(b), r.pb(r[c.se]), y.pb(c.fi);
	}
	s.clear();
	booga.clear();
	for (int i=0; i<y.size(); ++i)booga.pb(mp(y[i], i));
	sort(booga.begin(), booga.end(), greater<pii>());
	p=0;
	for (auto c:booga){
		while (p<h.size()&&ooga[p].fi>=c.fi)s.insert(ooga[p].se), ++p;
		int a=l[c.se], b=r[c.se];
		s.insert(a);
		s.insert(b);
		int prev=-1;
		vector<int> del;
		for (auto it=s.lower_bound(a); it!=s.end()&&*it<=b; ++it){
			if (vect[*it].size()){
				graph[vect[*it].back().se].pb(mp(counter, vect[*it].back().fi-c.fi));
				graph[counter].pb(mp(vect[*it].back().se, vect[*it].back().fi-c.fi));
			}
			vect[*it].pb(mp(c.fi, counter));
			if (prev!=-1){
				graph[counter-1].pb(mp(counter, x[*it]-x[prev]));
				graph[counter].pb(mp(counter-1, x[*it]-x[prev]));
			}
			prev=*it;
			++counter;
			if (*it!=a&&*it!=b)del.pb(*it);
		}
		for (auto a:del)s.erase(a);
	}
	if (vect[start].size()){
		graph[vect[start].back().se].pb(mp(counter, vect[start].back().fi));
		graph[counter].pb(mp(vect[start].back().se, vect[start].back().fi));
	}
	++counter;
	if (vect[end].size()){
		graph[vect[end].back().se].pb(mp(counter, vect[end].back().fi));
		graph[counter].pb(mp(vect[end].back().se, vect[end].back().fi));
	}
	++counter;
	vector<int> dist(counter, LLONG_MAX/2);
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	pq.push(mp(0, counter-2));
	while (pq.size()){
		int node=pq.top().se, d=pq.top().fi;
		pq.pop();
		if (d>=dist[node])continue;
		dist[node]=d;
		for (auto num:graph[node])pq.push(mp(d+num.se, num.fi));
	}
	return (dist[counter-1]==LLONG_MAX/2?-1:dist[counter-1]);
}

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