Submission #1216619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216619		brinton	Sky Walking (IOI19_walk)	C++20	0 / 100	1589 ms	1114112 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
// #include "grader.cpp"

using namespace std;
#define inf (long long)(1e16)
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	vector<array<int,3>> lines;
	for(int i = 0;i < x.size();i++){
		lines.push_back({h[i],2,i});
	}
	for(int i = 0;i < l.size();i++){
		lines.push_back({y[i],1,i});
	}

	vector<pair<int,int>> prev(x.size(),{-1,-1});


	sort(lines.begin(),lines.end());
	reverse(lines.begin(),lines.end());
	set<int> alr;
	int N = 0;
	vector<vector<pair<int,long long>>> edges(N);
	for(auto [h,type,idx]:lines){// high->low, building->bridge
		if(type == 2){
			// buildings
			alr.insert(idx);
			continue;
		}else{
			auto it1 = alr.lower_bound(l[idx]);
			auto it2 = alr.upper_bound(r[idx]);
			int lid = -1,lidx = -1;
			for(auto it = it1;it != it2;it++){
				// add new points
				// if(N >= 18) cout << "!!" << h << " " << type << " " << idx << endl;
				int cid = N;
				edges.push_back({});
				N++;
				auto [pid,ph] = prev[*it];
				if(pid != -1){
					edges[cid].push_back({pid,ph-h});
					edges[pid].push_back({cid,ph-h});
				}
				prev[*it] = {cid,h};
				
				if(lid != -1){
					edges[cid].push_back({lid,x[*it]-x[lidx]});
					edges[lid].push_back({cid,x[*it]-x[lidx]});
				}
				lid = cid,lidx = *it;
			}
		}
	}


	vector<int> floorId(x.size());
	for(int i = 0;i < x.size();i++){
		int cid = N;
		edges.push_back({});
		N++;
		auto [pid,ph] = prev[i];
		if(pid != -1){
			edges[cid].push_back({pid,ph});
			edges[pid].push_back({cid,ph});
		}
		floorId[i] = cid;
	}
	// do dijkstra
	vector<long long> dist(N,inf);
	dist[floorId[s]] = 0;
	priority_queue<pair<int,long long>,vector<pair<int,long long>>,greater<pair<int,long long>>> pq;// dist,idx
	pq.push({0,floorId[s]});
	
	
	while(!pq.empty()){
		auto [cdist,cur] = pq.top();
		pq.pop();
		if(dist[cur] != cdist) continue;
		for(auto [nxt,w]:edges[cur]){
			if(dist[cur]+w < dist[nxt]){
				dist[nxt] = dist[cur]+w;
				pq.push({dist[nxt],nxt});
			}
		}
	}

	// for(int i = 0;i < N;i++){
	// 	cout << i << ":";
	// 	for(auto [nxt,w]:edges[i]){
	// 		cout << "(" << nxt << "," << w << ") ";
	// 	}
	// 	cout << endl;
	// }
	// for(auto &i:floorId) cout << i << " ";cout << endl;
	// for(auto &i:dist) {
	// 	if(i == inf) cout << "-1 ";
	// 	else cout << i << " ";
	// }
	// cout << endl;
	if(dist[floorId[g]] == inf){
		return -1;
	}else{
		return dist[floorId[g]];
	}
}

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