Submission #1047673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047673		Alihan_8	Sky Walking (IOI19_walk)	C++17	33 / 100	799 ms	92532 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define ln '\n'

using i64 = long long;

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

const i64 inf = 1e15;

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) {
	{ // modification
		auto modify = [&](int u){
			int m = l.size();
			
			set <int> st;
			
			for ( int i = 0; i < m; i++ ){
				if ( y[i] <= h[u] && l[i] <= u && r[i] >= u ){
					l.pb(l[i]), r.pb(u); y.pb(y[i]);
					l.pb(u), r.pb(r[i]); y.pb(y[i]);
					st.insert(i);
				} 
			}
			
			vector <int> l_, r_, y_;
			
			for ( int i = 0; i < (int)l.size(); i++ ){
				if ( !st.count(i) ){
					l_.pb(l[i]), r_.pb(r[i]), y_.pb(y[i]);
				}
			}
			
			l = l_, r = r_, y = y_;
		};
		
		modify(s), modify(g);
	}
	
	int n = x.size(), m = l.size();
	
	vector <vector<ar<int,3>>> H(n);
	
	vector <vector<int>> qry(n);
	
	for ( int i = 0; i < m; i++ ){
		H[l[i]].pb({1, y[i], i});
		H[r[i]].pb({0, y[i], i});
		qry[r[i]].pb(i);
	}
	
	y.pb(0), l.pb(s), r.pb(s); // start
	y.pb(0), l.pb(g), r.pb(g); // end
	
	qry[s].pb(m), qry[g].pb(m + 1);
	
	vector <int> D(m + 2, -1), U(m + 2, -1);
	
	// m -> (0), m + 1 -> (n - 1)
	
	set <pair<int,int>> st;
	
	for ( int i = 0; i < n; i++ ){
		for ( auto &[t, u, j]: H[i] ){
			if ( t > 0 ){
				st.insert({u, j});
			} else if ( i + 1 < n ){ // for (n - 1, 0)
				st.erase({u, j});
			}
		}
		
		for ( auto &j: qry[i] ){
			auto it = st.lower_bound({y[j], -1});
			
			if ( it != st.end() ){
				U[j] = it -> second;
			}
			
			if ( it != st.begin() ){
				D[j] = prev(it) -> second;
			}
		}
	}
	
	//~ cout << "Up & Down : \n";
	//~ for ( int i = 0; i < m + 2; i++ ){
		//~ cout << U[i] << " " << D[i] << ln;
	//~ } cout << ln;
	
	vector <vector<int>> rng(m + 2);
	
	for ( int i = 0; i < m + 2; i++ ){
		rng[i].pb(l[i]);
		rng[i].pb(r[i]);
		
		if ( U[i] == i ) U[i] = -1;
		if ( D[i] == i ) D[i] = -1;
		
		if ( U[i] != -1 ){
			rng[U[i]].pb(r[i]);
		}
		
		if ( D[i] != -1 ){
			rng[D[i]].pb(r[i]);
		}
	}
	
	map <ar<int,2>,int> id;
	
	vector <vector<ar<i64,2>>> adj;
	
	int k = 0;
	
	auto get = [&](int u, int v){
		if ( !id.count({u, v}) ){
			id[{u, v}] = k++;
			adj.pb(vector <ar<i64,2>>());
		}
		
		return id[{u, v}];
	};
	
	for ( int i = 0; i < m + 2; i++ ){
		auto &p = rng[i];
		
		sort(all(p));
		p.resize(unique(all(p)) - p.begin());
		
		{ // assigning index
			for ( auto x: p ) get(x, y[i]); 
		}
		
		for ( int j = 0; j + 1 < (int)p.size(); j++ ){
			int u = get(p[j], y[i]), v = get(p[j + 1], y[i]);
			
			adj[u].pb({v, x[p[j + 1]] - x[p[j]]}); // to the right
			adj[v].pb({u, x[p[j + 1]] - x[p[j]]});
			
			//~ cout << "{" << p[j] << " " << y[i] << "}  {" << p[j + 1] << " " << y[i] << "}  " << x[p[j + 1]] - x[p[j]] << ln;
		}
		
		if ( D[i] != -1 ){ // down
			int u = get(r[i], y[i]), v = get(r[i], y[D[i]]);
			
			//~ cout << "{" << r[i] << " " << y[i] << "}  {" << r[i] << " " << y[D[i]] << "}  " << y[i] - y[D[i]] << ln; 
			
			adj[u].pb({v, y[i] - y[D[i]]});
			adj[v].pb({u, y[i] - y[D[i]]});
		} 
		
		if ( U[i] != -1 ){ // up
			int u = get(r[i], y[i]), v = get(r[i], y[U[i]]);
			
			//~ cout << "{" << r[i] << " " << y[i] << "}  {" << r[i] << " " << y[U[i]] << "}  " << -y[i] + y[U[i]] << ln; 
			
			adj[u].pb({v, -y[i] + y[U[i]]});
			adj[v].pb({u, -y[i] + y[U[i]]});
		}
	}
	
	vector <i64> dp(k, inf);
	
	priority_queue <ar<i64,2>> q;
	
	int u = get(s, 0);
	
	dp[u] = 0;
	q.push({0, u});
	
	while ( !q.empty() ){
		auto [val, u] = q.top();
		q.pop();
		
		if ( -val != dp[u] ) continue;
		
		for ( auto &[v, w]: adj[u] ){
			if ( chmin(dp[v], dp[u] + w) ){
				q.push({-dp[v], v});
			}
		}
	}
	
	u = get(g, 0);
	
	if ( dp[u] == inf ){
		dp[u] = -1;
	}
	
	return dp[u];
}

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