Submission #1075381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075381		HD1	Sky Walking (IOI19_walk)	C++14	0 / 100	1002 ms	343296 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(x) ll(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6+10;
const ll inf=1e9;
vector<ii>gfo[MAX];
ll cur[MAX], dist[MAX];
void dikstra(ll ini){
	set<ii> q;
	q.insert({0,ini});
	dist[ini]=0;
	while(sz(q)){
		auto x=*q.begin();
		q.erase(q.begin());
		ll u=x.ss;
		ll dist_u=x.ff;
		if(dist_u!=dist[u])continue;
		for(auto y:gfo[u]){
			ll w=y.ss;
			ll v=y.ff;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				q.insert({dist[v], v});
			}
		}
	}
}
map< pair<ll,ll>, ll> M;
long long min_distance(vector<int> x,vector<int> h,
	vector<int> l,vector<int> r, 
	vector<int> y, int s, int g) {
	vector<pair<int,ii>> c;
	ll m=sz(y);//numero de rascacielos
	ll n=sz(x);//numero de torres
	for(ll i=0; i<m; i++){
		c.pb({y[i],{l[i],r[i]}});// por su altura
	}
	sort(all(c));
	ll nod=0, nod_prev=0, mx=0, pos=0;
	for(ll i=0; i<n; i++){
		if(!M.count({x[i], 0})){
			M[{x[i],0}]=mx+1;
			mx++;
			cur[i]=0;//altura
		}
	}
	for(auto q:c){//rascacielo en la altura q.ff
		ll alt=q.ff;
		ll l=q.ss.ff;
		ll r=q.ss.ss;
		for(ll i=l; i<=r; i++){
			if(alt<=h[i]){// hay interseccion 
				if(!M.count({x[i],alt})){
					M[{x[i],alt}]=mx+1;
					mx++;
				}
				nod = M[{x[i], alt}];
				// verical
				gfo[nod].pb({M[{x[i],cur[i]}], alt-cur[i]});
				gfo[M[{x[i],cur[i]}]].pb({nod, alt-cur[i]});
				cur[i]=alt; 
				if(i==l){
					nod_prev=nod;
					pos=x[l];
					continue;
				}
				//horizontal
				gfo[nod].pb({nod_prev,x[i]-pos});
				gfo[nod_prev].pb({nod,x[i]-pos});
				pos = x[i];// ultima posicion de interseccion
				nod_prev = nod;// nombre del nodo anterior
			}
		}
	}
	// for(auto a:M){
	// 	cout<<a.ff.ff<<' '<<a.ff.ss<<" -> "<<a.ss<<'\n';
	// }
	// for(auto a:M){
	// 	cout<<a.ss<<" -> ";
	// 	for(auto b:gfo[a.ss]){
	// 		cout<<b.ff<<", "<<b.ss;
	// 		cout<<'\n';
	// 	}
	// 	cout<<'\n';
	// }
	for(ll i=0; i<=mx; i++)dist[i]=inf;
	dikstra(M[{x[s],0}]);
	ll ans=dist[M[{x[g],0}]];
	return ans;
}

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