Submission #1239126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239126		Ludissey	Sky Walking (IOI19_walk)	C++20	24 / 100	3080 ms	1114112 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;


int gdist(pair<int,int> a, pair<int,int> b){
	return (abs(a.first-b.first)+abs(a.second-b.second));
}

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<pair<int,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;
	int k=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,k});
			neighB[(*it).second].push_back({i+n,k});
			k++;
			it++;
		}
	}
	vector<pair<int,int>> inter(k+n);
	vector<vector<int>> neigh(n+k);
	s=k+s;
	g=k+g;
	for (int i = 0; i < n; i++)
	{
		inter[k+i]={building[i].second,0};
		int last=k+i;
		for (int j = sz(neighB[i])-1; j>=0; j--)
		{
			neigh[last].push_back(neighB[i][j].second);
			neigh[neighB[i][j].second].push_back(last);
			inter[neighB[i][j].second]={building[i].second,bridge[neighB[i][j].first-n].first};
			last=neighB[i][j].second;
		}

	}
	for (int i = n; i < n+m; i++)
	{
		for (int j = 1; j<sz(neighB[i]); j++)
		{
			neigh[neighB[i][j].second].push_back(neighB[i][j-1].second);
			neigh[neighB[i][j-1].second].push_back(neighB[i][j].second);
		}

	}
	vector<int> dist(k+n,1e17);
	vector<bool> visit(k+n);
	priority_queue<pair<int,int>> pq;
	dist[s]=0;
	pq.push({0,s});
	while(!pq.empty()){
		int u=pq.top().second; pq.pop();
		if(visit[u]==true) continue;
		visit[u]=true; 
		//cerr << inter[u].first << " " << inter[u].second << ": " << dist[u] << "\n";
		for (auto v : neigh[u])
		{
			int cst=gdist(inter[u],inter[v]);
			if(dist[v]>cst+dist[u]) {
				dist[v]=cst+dist[u];
				pq.push({-dist[v],v});
			}
		}
	}
	if(dist[g]==1e17) return -1;
	return dist[g];
}

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