Submission #723956

#	Time	Username	Problem	Language	Result	Execution time	Memory
723956		alvingogo	Sky Walking (IOI19_walk)	C++14	24 / 100	4054 ms	472628 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int S, int T) {
	int n=x.size(),m=l.size();
	vector<pair<int,int> > g(n);
	for(int i=0;i<n;i++){
		g[i]={h[i],i};
	}
	sort(g.begin(),g.end());
	vector<pair<pair<int,int>,int> > e(m);
	for(int i=0;i<m;i++){
		e[i]={{l[i],r[i]},y[i]};
	}
	sort(e.begin(),e.end(),[&](auto a,auto b){return a.sc<b.sc;});
	set<int> s;
	for(int i=0;i<n;i++){
		s.insert(i);
	}
	int dl=0;
	map<pair<int,int>,int> mp;
	int cnt=0;
	vector<vector<pair<int,int> > > re;
	re.reserve(2400000);
	for(int i=0;i<n;i++){
		mp[pii(i,0)]=cnt;
		cnt++;
		re.push_back(vector<pair<int,int> >());
	}
	for(int i=0;i<m;i++){
		while(dl<n && g[dl].fs<e[i].sc){
			s.erase(g[dl].sc);
			dl++;
		}
		int nw=-1;
		for(auto it=s.lower_bound(e[i].fs.fs);(*it)!=e[i].fs.sc;it++){
			if(nw==-1){
				if(mp.find({*it,e[i].sc})==mp.end()){
					mp[pii(*it,e[i].sc)]=cnt;
					cnt++;
					re.push_back(vector<pair<int,int> >());
				}
				nw=mp[pii(*it,e[i].sc)];
			}
			auto nxt=next(it);
			if(mp.find({*nxt,e[i].sc})==mp.end()){
				mp[pii(*nxt,e[i].sc)]=cnt;
				cnt++;
				re.push_back(vector<pair<int,int> >());
			}
			int to=mp[{*nxt,e[i].sc}],val=(x[*nxt]-(x[*it]));
			re[nw].push_back({to,val});
			re[to].push_back({nw,val});
			nw=to;
		}
	}
	pair<int,int> nwh={-1,0};
	for(auto h:mp){
		if(h.fs.sc){
			re[h.sc].push_back({nwh.fs,h.fs.sc-nwh.sc});
			re[nwh.fs].push_back({h.sc,h.fs.sc-nwh.sc});
		}
		nwh={h.sc,h.fs.sc};
	}
	vector<ll> dis(mp.size(),1e18);
	int st=mp[pii(S,0)],ed=mp[pii(T,0)];
	dis[st]=0;
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
	pq.push({0,st});
	while(pq.size()){
		auto c=pq.top();
		pq.pop();
		for(auto z:re[c.sc]){
			if(dis[z.fs]>c.fs+z.sc){
				dis[z.fs]=c.fs+z.sc;
				pq.push({dis[z.fs],z.fs});
			}
		}
	}
	if(dis[ed]>5e17){
		return -1;
	}
	return dis[ed];
}

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