Submission #767932

#	Time	Username	Problem	Language	Result	Execution time	Memory
767932		khshg	Sky Walking (IOI19_walk)	C++14	10 / 100	4081 ms	608392 KiB

walk

#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second
 
#define ar array
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
 
#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)
 
template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }
 
V<vpi> adj;
 
const long long INF = 0x3f3f3f3f3f3f3f3f; // here

void Dijkstra(int st, vector<long long>& D) { // here Dis type
	int n = (int) sz(adj);
	D.resize(n, INF); // make sure to declare larger #INF# for long long
	auto cmp = [&D] (const int& a, const int& b) -> bool { return (D[a] < D[b] || (D[a] == D[b] && a < b)); };
	set<int, decltype(cmp)> s(cmp);
	D[st] = 0;
	s.insert(st);
	while(!s.empty()) {
		int cur = *begin(s);
		s.erase(begin(s));
		for(auto& u : adj[cur]) {
			int to = u.first;
			long long len = u.second; // here
			if(D[cur] + len < D[to]) {
				s.erase(to);
				D[to] = D[cur] + len;
				s.insert(to);
			}
		}
	}
}
 
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int N = sz(x);
	V<vi> up(N, vi{0});
	map<pi, int> nodes;
	F0R(i, N) nodes[mp(x[i], 0)];
	int M = sz(l);
	F0R(i, M) {
		FOR(cur, l[i], r[i] + 1) {
			if(h[cur] >= y[i]) {
				nodes[mp(x[cur], y[i])];
				up[cur].pb(y[i]);
			}
		}
	}
	int tim3 = 0; trav(u, nodes) u.ss = tim3++;
	adj.rsz(sz(nodes));
	F0R(i, N) {
		sor(up[i]);
		up[i].erase(unique(all(up[i])), end(up[i]));
		F0R(j, sz(up[i]) - 1) {
			adj[nodes[mp(x[i], up[i][j])]].eb(nodes[mp(x[i], up[i][j + 1])], up[i][j + 1] - up[i][j]);
			adj[nodes[mp(x[i], up[i][j + 1])]].eb(nodes[mp(x[i], up[i][j])], up[i][j + 1] - up[i][j]);
		}
	}
	F0R(i, M) {
		pi prev = {-1, -1};
		FOR(cur, l[i], r[i] + 1) {
			if(h[cur] >= y[i]) {
				if(prev != mp(-1, -1)) {
					adj[nodes[prev]].eb(nodes[mp(x[cur], y[i])], x[cur] - prev.ff);
					adj[nodes[mp(x[cur], y[i])]].eb(nodes[prev], x[cur] - prev.ff);
				}
				prev = mp(x[cur], y[i]);
			}
		}
	}
	vl dis;
	Dijkstra(nodes[mp(x[s], 0)], dis);
	if(dis[nodes[mp(x[g], 0)]] == INF) return -1;
	return dis[nodes[mp(x[g], 0)]];
}

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