제출 #1045053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045053		Alihan_8	Sky Walking (IOI19_walk)	C++17	57 / 100	4059 ms	892548 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) {
	int n = x.size(), m = l.size();
	
	if ( s == 0 && g == n - 1 ){ // subtask #3
		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(0), r.pb(0); // start
		y.pb(0), l.pb(n - 1), r.pb(n - 1); // end
		
		qry[0].pb(m), qry[n - 1].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(0, 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(n - 1, 0);
		
		if ( dp[u] == inf ){
			dp[u] = -1;
		}
		
		return dp[u];
	} else{
		vector <vector<ar<int,3>>> H(n + 1);
	
		{ // shifting y
			y.pb(0);
			for ( int i = m; i > 0; i-- ){
				y[i] = y[i - 1];
			} y[0] = 0;
		}
		
		for ( int i = 1; i <= m; i++ ){
			H[l[i - 1]].pb({1, y[i], i});
			H[r[i - 1] + 1].pb({0, y[i], i});
		}
		
		set <pair<int,int>> st;
		
		vector <vector<int>> a(n, {0}), mp(m + 1);
		
		auto V = a;
		
		for ( int i = 0; i < n; i++ ){
			for ( auto &[t, y, j]: H[i] ){
				if ( t > 0 ){
					st.insert({y, j});
				} else st.erase({y, j});
			}
			
			auto it = st.begin();
			
			while ( it != st.end() && it -> first <= h[i] ){
				a[i].pb(it -> second);
				V[i].pb(it -> first);
				mp[it -> second].pb(i);
				it = next(it);
			}
		}
		
		vector <vector<i64>> dp(n);
		vector <vector<int>> id(n);
		
		for ( int i = 0; i < n; i++ ){
			sort(all(a[i]), [&](int &u, int &v){
				return y[u] < y[v];
			});
			
			int s = a[i].size();
			dp[i].resize(s, inf);
			id[i].resize(s);
			
			for ( int j = 1; j < s; j++ ){
				int x = a[i][j];
				
				id[i][j] = lower_bound(all(mp[x]), i) - mp[x].begin();
			}
		}
		
		dp[s][0] = 0;
		
		priority_queue <ar<i64,3>> q;
		
		q.push({0, s, 0});
		
		while ( !q.empty() ){
			auto [val, u, j] = q.top();
			q.pop();
			
			if ( -val != dp[u][j] ) continue;
			
			if ( j != 0 ){ // using skywalk a[u][j]
				int t = a[u][j];
				
				for ( auto i: {id[u][j] - 1, id[u][j] + 1} ){
					
					if ( i < 0 || i >= (int)mp[t].size() ){
						continue;
					}
					
					int v = mp[t][i], nxt = lower_bound(all(V[v]), y[t]) - V[v].begin();
					
					if ( chmin(dp[v][nxt], dp[u][j] + abs(x[v] - x[u])) ){
						q.push({-dp[v][nxt], v, nxt});
					}
				}
			}
			
			for ( auto i: {j + 1, j - 1} ){
				if ( i < 0 || i >= (int)dp[u].size() ){
					continue;
				}
				
				if ( chmin(dp[u][i], dp[u][j] + abs(y[a[u][j]] - y[a[u][i]])) ){
					q.push({-dp[u][i], u, i});
				}
			}
		}
		
		i64 ans = dp[g][0];
		
		if ( ans == inf ){
			ans = -1;
		}
		
		return ans;
	}
}

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