Submission #144441

#	Time	Username	Problem	Language	Result	Execution time	Memory
144441		qkxwsm	Sky Walking (IOI19_walk)	C++14	24 / 100	1930 ms	600652 KiB

walk

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 2000013
#define INF 1000000007
#define LLINF 2696969696969696969

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, S, T, V;
pll arr[MAXN];
vpl edge[MAXN];
vpl edge1[MAXN];
vl hs[MAXN];
vector<array<ll, 3> > events;
set<int> s;
int st[MAXN];
ll dist[MAXN];
ll ans;

ll dijkstra()
{
	S = st[S]; T = st[T];
	priority_queue<pll, vector<pll>, greater<pll> > q;
	FOR(i, 0, V) dist[i] = LLINF;
	// FOR(i, 0, V)
	// {
	// 	for (auto e : edge1[i])
	// 	{
	// 		cerr << i << " -> " << e.se << " len " << e.fi << endl;
	// 	}
	// }
	dist[S] = 0; q.push({0, S});
	while(!q.empty())
	{
		ll d = q.top().fi; int u = q.top().se; q.pop();
		if (u == T) break;
		if (d != dist[u]) continue;
		for (auto e : edge1[u])
		{
			ll nd = d + e.fi; int v = e.se;
			if (dist[v] > nd)
			{
				dist[v] = nd;
				q.push({nd, v});
			}
		}
	}
	return dist[T];
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int source, int sink)
{
	N = SZ(x);
	FOR(i, 0, N)
	{
		arr[i] = {x[i], h[i]};
	}
	M = SZ(y);
	FOR(i, 0, M)
	{
		int u = l[i], v = r[i]; ll h = y[i];
		edge[u].PB({h, v});
		edge[v].PB({h, u});
	}
	S = source; T = sink;
	FOR(i, 0, N)
	{
		events.PB({arr[i].se, INF, i});
		for (auto p : edge[i])
		{
			if (p.se < i) continue;
			events.PB({p.fi, i, p.se});
		}
		hs[i].PB(0);
		hs[i].PB(arr[i].se);
	}
	sort(ALL(events));
	reverse(ALL(events));
	FOR(i, 0, SZ(events))
	{
		auto e = events[i];
		if (e[1] == INF)
		{
			s.insert(e[2]); continue;
		}
		else
		{
			int u = e[1], v = e[2];
			// cerr << u << " -> " << v << endl;
			for (auto it = s.UB(u); *it != v; it++)
			{
				hs[*it].PB(e[0]);
			}
			hs[u].PB(e[0]);
			hs[v].PB(e[0]);
		}
	}
	FOR(i, 0, N)
	{
		sort(ALL(hs[i]));
		hs[i].erase(unique(ALL(hs[i])), hs[i].end());
		st[i] = V;
		V += SZ(hs[i]);
		// cerr << "X COOR " << arr[i].fi << endl;
		// for (int x : hs[i])
		// {
		// 	cerr << x << ' ';
		// }
		// cerr << endl;
		// cerr << "ST " << i << " = " << st[i] << endl;
	}
	// cerr << "V = " << V << endl;
	st[N] = V;
	FOR(i, 0, N)
	{
		FOR(j, st[i], st[i + 1] - 1)
		{
			ll dy = hs[i][j + 1 - st[i]] - hs[i][j - st[i]];
			edge1[j].PB({dy, j + 1});
			edge1[j + 1].PB({dy, j});
		}
	}
	s.clear();
	FOR(i, 0, SZ(events))
	{
		auto e = events[i]; ll h = e[0];
		if (e[1] == INF)
		{
			s.insert(e[2]); continue;
		}
		else
		{
			int u = e[1], v = e[2];
			for (auto it = s.LB(u); *it != v; it++)
			{
				int x = *it, y = *(next(it));
				int idx = st[x] + LB(ALL(hs[x]), h) - hs[x].begin();
				int idy = st[y] + LB(ALL(hs[y]), h) - hs[y].begin();
				edge1[idx].PB({arr[y].fi - arr[x].fi, idy});
				edge1[idy].PB({arr[y].fi - arr[x].fi, idx});
			}
		}
	}
	ans = dijkstra();
	if (ans >= LLINF) return -1;
	return ans;
}

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