Submission #955094

#	Time	Username	Problem	Language	Result	Execution time	Memory
955094		waldi	Sky Walking (IOI19_walk)	C++17	0 / 100	4045 ms	622356 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define inf 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e){
	int n = ssize(x);
	int m = ssize(l);
	
	vector<vector<pii>> g;
	vector<map<int, int>> vec_map(n);
	auto konwersja = [&](int poz, int wys){
		if(!vec_map[poz][wys]) g.emplace_back(), vec_map[poz][wys] = ssize(g);
		return vec_map[poz][wys]-1;
	};
	
	int start = konwersja(s, 0);
	int meta = konwersja(e, 0);
	
	vector<pii> akt(n);
	REP(i, n) akt[i] = {h[i], i};
	sort(rall(akt));
	
	vector<pii> polaczenia(m);
	REP(i, m) polaczenia[i] = {y[i], i};
	sort(rall(polaczenia));
	
	int iter = 0;
	set<int> zapalone;
	for(auto [wys, i] : polaczenia){
		while(iter < ssize(akt) && akt[iter].fi >= wys) zapalone.emplace(akt[iter].se), ++iter;
		int lewo = l[i], prawo = r[i];
		for(auto it = zapalone.find(lewo); *it != prawo; it = next(it)){
			int a = konwersja(*it, wys);
			int b = konwersja(*next(it), wys);
			int c = x[*next(it)]-x[*it];
			g[a].emplace_back(b, c);
			g[b].emplace_back(a, c);
			//~ printf("kr: %d %d  %d\n", a, b, c);
		}
	}
	
	for(auto mapa : vec_map){
		pii pop = {-1, -1};
		for(pii ja : mapa){
			if(pop.fi >= 0){
				int a = pop.se-1;
				int b = ja.se-1;
				int c = ja.fi-pop.fi;
				g[a].emplace_back(b, c);
				g[b].emplace_back(a, c);
				//~ printf("kr: %d %d  %d\n", a, b, c);
			}
			pop = ja;
		}
	}
	
	int siz = ssize(g);
	vector<ll> odl(siz, inf);
	priority_queue<pli> pq;
	odl[start] = 0ll, pq.emplace(0ll, start);
	while(ssize(pq)){
		int w = pq.top().se;
		ll c = -pq.top().fi;
		pq.pop();
		if(odl[w] != c) continue;
		for(pii i : g[w]) if(ll t = odl[w]+i.se; t < odl[i.fi]){
			odl[i.fi] = t, pq.emplace(-t, i.fi);
		}
	}
	return odl[meta];
}

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