Submission #1070714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070714		Gray	Sky Walking (IOI19_walk)	C++17	24 / 100	3488 ms	1048576 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define ln "\n"
#define ll long long
#define ld long double
const ll inf=2e18;
struct Graph{
	vector<vector<pair<ll, ll>>> A;
	vector<pair<ll, ll>> id;
	ll sz, ind;
	Graph(){
		sz=0; ind=0;
	}
	ll add_node(ll x, ll y){
		A.push_back(vector<pair<ll, ll>>());
		id.push_back({x, y});
		ind++; sz++;
		return ind-1;
	}
	void add_edge(ll u, ll v, ll w){
		A[u].push_back({v, w});
		A[v].push_back({u, w});
	}
	ll shortest(ll s, ll g){
		vector<ll> dist(sz, -1);
		set<pair<ll, ll>> que;
		que.insert({0, s});
		while (!que.empty()){
			auto cur = *que.begin();
			que.erase(que.begin());
			if (dist[cur.ss]!=-1) continue;
			dist[cur.ss]=cur.ff;
			for (auto v:A[cur.ss]){
				if (dist[v.ff]==-1) que.insert({cur.ff+v.ss, v.ff});
			}
		}
		return dist[g];
	}
	void debug(){
		for (ll i=0; i<sz; i++){
			cout << id[i].ff << "," << id[i].ss << ": ";
			for (auto v:A[i]){
				cout << id[v.ff].ff << "," << id[v.ff].ss << "-" << v.ss << " ";
			}
			cout << ln;
		}
	}
};

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) {
	ll n = x.size(), m=l.size();
	set<pair<ll, pair<ll, ll>>> bd;
	Graph gr;

	for (ll i=0; i<n; i++){
		ll cn = gr.add_node(x[i], 0);
		if (i==s) s=cn;
		if (i==g) g=cn;
		bd.insert({i, {cn, 0}});
	}
	map<ll, pair<vector<ll>, vector<ll>>> ev;
	for (ll i=0; i<n; i++){
		ev[h[i]].ss.push_back(i);
	}
	for (ll i=0; i<m; i++){
		ev[y[i]].ff.push_back(i);
	}
	for (auto &[height, data]:ev){
		for (auto bi:data.ff){
			auto cur = bd.lower_bound({l[bi], {-1, -1}});
			ll prev=-1, prevx=-1;
			// cout << l[bi] << " " << r[bi] << " -> " << (*cur).ff << endl;
			// continue;
			while ((*cur).ff<=r[bi] and (*cur).ff>=l[bi]){
				// cout << &cur << endl;
				ll ti = (*cur).ff;
				if ((*cur).ss.ss<y[bi]){
					ll nw = gr.add_node(x[ti], y[bi]);
					gr.add_edge(nw, (*cur).ss.ff, y[bi]-(*cur).ss.ss);
					bd.erase(cur);
					bd.insert({ti, {nw, y[bi]}});
					cur = bd.find({ti, {nw, y[bi]}});
				}
				if (prev!=-1){
					gr.add_edge(prev, (*cur).ss.ff, x[ti]-prevx);
				}
				prevx=x[ti]; prev=(*cur).ss.ff;
				if ((*cur)==*bd.rbegin()) break;
				cur++;
			}
		}
		for (auto hsi:data.ss){
			bd.erase(bd.lower_bound({hsi, {-1, -1}}));
		}
	}
	// gr.debug();
	return gr.shortest(s, g);
}

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