제출 #1048888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048888		fuad27	Sky Walking (IOI19_walk)	C++17	0 / 100	4070 ms	456156 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
long long min_distance(std::vector<int> x, std::vector<int> h,
std::vector<int> l, std::vector<int> r, std::vector<int> y, int st, int ed) {
#define int long long
	int n = h.size();
	int m = y.size();
	vector<int> bl;
	vector<int> br(m);
	bl.resize(n);
	iota(bl.begin(),bl.end(), 0);
	iota(br.begin(),br.end(), 0);
	sort(bl.begin(), bl.end(), [&](int u, int v) -> bool {
		return h[u] > h[v];
	});
	sort(br.begin(), br.end(), [&](int u, int v) -> bool {
		return y[u] > y[v];
	});
	int p1 = 0;
	set<int> s;
	map<int,vector<int>> mp;
	map<int,vector<int>> coords;



	vector<vector<pair<int,long long>>> g;
	
	map<pair<int,int>, int> cmp;
	auto add = [&](int x, int y) -> int {
		if(cmp.find(pair<int,int>(x, y))!=cmp.end())return cmp[{x, y}];
		cmp[{x,y}]=g.size();
		coords[x].push_back(y);
		g.push_back({});
		return cmp[{x,y}];
	};
	for(int i = 0;i<m;i++) {
		while(p1 < n and h[bl[p1]] >= y[br[i]]) {
			mp[x[bl[p1]]].push_back(bl[p1]);
			s.insert(x[bl[p1++]]);	
		}
		int prev=-1;
		for(auto it = s.lower_bound(x[l[br[i]]]);it!=s.end();it++) {
			if((*it) > x[r[br[i]]])break;
			int at = (*it);
			if(coords[at].size())
			coords[at].push_back(y[br[i]]);
			else coords[at].push_back(0);
			add(at, y[br[i]]);
			add(at, 0);
			if(prev!=-1) {
				g[add(prev, y[br[i]])].push_back({add(at, y[br[i]]), abs(at-prev)});
				g[add(at, y[br[i]])].push_back({add(prev, y[br[i]]), abs(at-prev)});
			}
			prev=at;
		}
	}
	for(auto &i:coords) {
		sort(i.second.begin(), i.second.end());
		for(int j = 1;j<(int)(i.second).size();j++) {
			g[add(i.first, i.second[j-1])].push_back({add(i.first, i.second[j]), abs(i.second[j]-i.second[j-1])});
			g[add(i.first, i.second[j])].push_back({add(i.first, i.second[j-1]), abs(i.second[j]-i.second[j-1])});
		}
	}
	priority_queue<pair<long long,int>> pq;
	pq.push(pair<long long, int>(0ll, add(x[st], 0)));
	vector<long long> dist(g.size(), (long long)2e18);
	dist[add(x[st], 0)] = 0;

	map<int, pair<int,int>> revs;
	for(auto i:cmp) {
		revs[i.second] = i.first;
	}
	vector<bool> vis(g.size());
	while(pq.size()) {
		int at = pq.top().second;
		pq.pop();
		if(vis[at])continue;
		vis[at]=1;
//		cout << revs[at].first << " " << revs[at].second << " " << dist[at] << endl;
		for(auto [to, w]:g[at]){ 
			if(dist[to] > dist[at] + w) {
				dist[to] = dist[at]+w;
				pq.push(pair<long long, int> (-dist[to], to));
			}
		}
	}
	return dist[add(x[ed], 0)];
#undef int
}

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