Submission #767886

#	Time	Username	Problem	Language	Result	Execution time	Memory
767886		khshg	Sky Walking (IOI19_walk)	C++14	10 / 100	4094 ms	643300 KiB

walk

#include "walk.h"
#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<vpl> adj;

const long long INF = 0x3f3f3f3f3f3f3f3f; // here

void Dijkstra(int st, vector<long long>& D, vector<int>& P) { // here Dis type
	int n = (int) sz(adj);
	D.resize(n, INF); // make sure to declare larger #INF# for long long
	P.resize(n, -1);
	using tp = pair<long long, int>; // here
	priority_queue<tp, vector<tp>, greater<tp>> pq;
	pq.push({0, st});
	D[st] = 0;
	while(!pq.empty()) {
		long long D_to_cur = pq.top().first; // here
		int cur = pq.top().second;
		pq.pop();
		if(D_to_cur != D[cur]) {
			continue;
		}
		for(auto& u : adj[cur]) {
			int to = u.first;
			long long len = u.second; // here
			if(D[cur] + len < D[to]) {
				D[to] = D[cur] + len;
				P[to] = cur;
				pq.push({D[to], to});
			}
		}
	}
}

vector<int> Restore_Path(int st, int en, vector<int>& P) {
	vector<int> path;
	while(en != st) {
		path.push_back(en);
		en = P[en];
	}
	path.push_back(st);
	reverse(begin(path), end(path));
	return path;
}

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]);
			}
		}
	}
	vpi inv;
	{
		int tim3 = 0; trav(u, nodes) u.ss = tim3++;
		inv.rsz(tim3);
		trav(u, nodes) {
			inv[u.ss] = u.ff;
		}
	}
	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;
	vi path;
	Dijkstra(nodes[mp(x[s], 0)], dis, path);
	if(dis[nodes[mp(x[g], 0)]] == INF) return -1;
	return dis[nodes[mp(x[g], 0)]];
}/*

int main() {
	int n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	int s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}*/

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