Submission #1216816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216816		loiiii12358	Sky Walking (IOI19_walk)	C++20	10 / 100	18 ms	2884 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int cnt;
map<pair<int,int>,int> tran;
vector<set<int>> nodes;
vector<vector<pair<int,int>>> edges;
priority_queue<pair<int,int>> pq;
vector<int> dist;

long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g) {
	int n=x.size(),m=l.size();
	edges.resize(n*m);nodes.resize(n);
	for(int i=0;i<m;i++){
		int last=-1;
		for(int j=l[i];j<=r[i];j++){
			if(h[j]>=y[i]){
				if(!tran.count({x[j],y[i]})){
					tran[{x[j],y[i]}]=cnt++;
					nodes[j].insert(y[i]);
				}
				if(last!=-1){
					edges[tran[{x[j],y[i]}]].push_back({tran[{x[last],y[i]}],x[j]-x[last]});
					edges[tran[{x[last],y[i]}]].push_back({tran[{x[j],y[i]}],x[j]-x[last]});
				}
				last=j;
			}
		}
	}
	tran[{x[s],0}]=cnt++;tran[{x[g],0}]=cnt++;
	nodes[s].insert(0);nodes[g].insert(0);
	for(int i=0;i<n;i++){
		int last=-1;
		for(auto j:nodes[i]){
			if(last!=-1){
				edges[tran[{x[i],last}]].push_back({tran[{x[i],j}],j-last});
				edges[tran[{x[i],j}]].push_back({tran[{x[i],last}],j-last});
			}
			last=j;
		}
	}
	dist.resize(cnt,1e18);
	pq.push({0,tran[{x[s],0}]});
	dist[tran[{x[s],0}]]=0;
	while(!pq.empty()){
		int u=pq.top().second,t=-pq.top().first;
		pq.pop();
		if(dist[u]!=t){
			continue;
		}
		for(int i=0;i<edges[u].size();i++){
			int v=edges[u][i].first;
			if(dist[v]>t+edges[u][i].second){
				dist[v]=t+edges[u][i].second;
				pq.push({-dist[v],v});
			}
		}
	}
	// for(auto i:tran){
	// 	cout << i.first.first << ' ' << i.first.second << ' ' << i.second << '\n';
	// }
	if(dist[tran[{x[g],0}]]==1e18){
		return -1;
	}
	return dist[tran[{x[g],0}]];
}

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