Submission #292846

#	Time	Username	Problem	Language	Result	Execution time	Memory
292846		miss_robot	Sky Walking (IOI19_walk)	C++14	10 / 100	55 ms	6136 KiB

walk

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

#pragma GCC optimize("O3")
#define ll long long

using namespace std;

const int N = 100000;
const ll INF = numeric_limits<ll>::max()/4;
int n, m, s, e;
int x[N], h[N], l[N], r[N], y[N];

ll st1(){
	map< int, set< pair<int, int> > > mp;
	vector<int> yv;
	for(int i = 0; i < m; i++){
		if(!mp.count(y[i])) yv.push_back(y[i]);
		mp[y[i]].insert({l[i], r[i]});
	}
	sort(yv.begin(), yv.end());
	m = yv.size();
	vector< vector< pair<int, ll> > > g(n*(m+1));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(h[i] < yv[j]) break;
			if(j) g[i*(m+1)+j].push_back({i*(m+1)+j-1, yv[j]-yv[j-1]});
			else g[i*(m+1)+j].push_back({i*(m+1)+m, yv[j]});
			if(j < m-1) g[i*(m+1)+j].push_back({i*(m+1)+j+1, yv[j+1]-yv[j]});
			auto it = mp[yv[j]].lower_bound({i, 0});
			if(it != mp[yv[j]].end() && it->first == i){
				int nxt = i+1;
				for(; h[nxt] < yv[j]; nxt++);
				g[i*(m+1)+j].push_back({nxt*(m+1)+j, x[nxt]-x[i]});
			}
			if(it != mp[yv[j]].begin() && (--it)->second >= i){
				int nxt = i-1;
				for(; h[nxt] < yv[j]; nxt--);
				g[i*(m+1)+j].push_back({nxt*(m+1)+j, x[i]-x[nxt]});
				if(it->second > i){
					nxt = i+1;
					for(; h[nxt] < yv[j]; nxt++);
					g[i*(m+1)+j].push_back({nxt*(m+1)+j, x[nxt]-x[i]});
				}
			}
		}
		g[i*(m+1)+m].push_back({i*(m+1), yv[0]});
	}
	vector<ll> dis(n*(m+1), INF);
	vector<int> vis(n*(m+1));
	priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > q;
	dis[s*(m+1)+m] = 0;
	q.push({0, s*(m+1)+m});
	while(!q.empty()){
		int u = q.top().second, v;
		ll w;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		if(u == e*(m+1)+m) return dis[u];
		for(auto &t : g[u]){
			tie(v, w) = t;
			if(dis[v] > dis[u]+w){
				dis[v] = dis[u]+w;
				q.push({dis[v], v});
			}
		}
	}
	return -1;
}

void wrt(vector<int>& X, vector<int>& H, vector<int>& L, vector<int>& R, vector<int>& Y, int S, int G){
	for(int i = 0; i < n; i++) x[i] = X[i], h[i] = H[i];
	for(int i = 0; i < m; i++) l[i] = L[i], r[i] = R[i], y[i] = Y[i];
	s = S, e = G;
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	n = x.size(), m = y.size();
	wrt(x, h, l, r, y, s, g);
	if(n <= 50 && m <= 50) return st1();
	return 0;
}

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