Submission #1239081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239081		Ludissey	Sky Walking (IOI19_walk)	C++20	0 / 100	4098 ms	141660 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n,m;

long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	n=sz(x);
	m=sz(l);
	vector<vector<int>> neighB(n+m);
	vector<pair<int,pair<int,int>>> bridge(m); // (y, (l,r))
	vector<pair<int,int>> building(n); // (h,x)
	for (int i = 0; i < n; i++) building[i]={h[i],x[i]};
	s=x[s];
	g=x[g];
	for (int i = 0; i < m; i++) bridge[i]={y[i],{x[l[i]],x[r[i]]}};
	sort(rall(building));
	sort(rall(bridge));
	for (int i = 0; i < n; i++) { if(building[i].second==s){ s=i; break; } }
	for (int i = 0; i < n; i++) { if(building[i].second==g){ g=i; break; } }
	set<pair<int,int>> buildset; //(x, i)
	int j=0;
	for (int i = 0; i < m; i++)
	{
		while(j<n&&building[j].first>=bridge[i].first){
			buildset.insert({building[j].second,j});
			j++;
		}
		auto it=buildset.lower_bound({bridge[i].second.first,-1});
		while(it!=buildset.end()&&(*it).first<=bridge[i].second.second){
			neighB[i+n].push_back((*it).second);
			neighB[(*it).second].push_back(i+n);
			it++;
		}
	}
	map<pair<int,int>,int> dist;
	map<pair<int,int>,bool> visit;
	priority_queue<pair<int,pair<int,int>>> pq;
	dist[{s,0}]=0;
	pq.push({0,{s,0}});
	int mn=1e18;
	while(!pq.empty()){
		pair<int,pair<int,int>> u=pq.top(); pq.pop();
		if(visit[u.second]==true) continue;
		visit[u.second]=true; 
		int ps=0;
		u.first=-u.first;
		if(u.second.first<n) { ps=building[u.second.first].second;  }
		else { ps=bridge[u.second.first-n].first;  }
		if(u.second.first==g) {
			mn=min(mn,u.first+u.second.second);
		}
		for (auto v : neighB[u.second.first])
		{
			int cst=0;
			if(v<n) cst=building[v].second;
			else cst=bridge[v-n].first;
			cst=abs(u.second.second-cst);
			int d=dist[{v,ps}];
			if(d==0||d>cst+u.first){
				d=cst+u.first;
				dist[{v,ps}]=d;
				pq.push({-d,{v,ps}});
			}
		}
	}
	return mn;
}

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