제출 #1220271

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

walk

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

#define ll long long

ll hf(ll x, ll y){
	return x*pow(10, 6)+y;
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
    int n = x.size();
	//for (int i=0; i<n; i++) h[i] = pow(10, 9);
	int m = l.size();
	vector<vector<int>> cp(m*2), ip(m);
	vector<vector<int>> ev;
	for (int i=0; i<m; i++){
		ev.push_back({l[i], 1, i});
		ev.push_back({r[i], -1, i});
	}
	set<int> hs;
	map<int,int> htw;
	sort(ev.begin(), ev.end());
	int i = 0;
	while (i < (int)ev.size()){
		int ct = ev[i][0];
		set<int> rm, in;
		while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == -1){
			hs.erase(y[ev[i][2]]);
			rm.insert(ev[i][2]);
            i++;
		}
		while (i < (int)ev.size() && ev[i][0] == ct && ev[i][1] == 1){
			hs.insert(y[ev[i][2]]);
			htw[y[ev[i][2]]] = ev[i][2];
			in.insert(ev[i][2]);
            i++;
		}
		for (int w : rm){
			auto it = hs.upper_bound(y[w]);
			if (it != hs.end()) cp[w].push_back(htw[*it]);
			if (it != hs.begin()){
				it--;
				cp[w].push_back(htw[*it]);
				if (*it == y[w] && it != hs.begin()){
					it--;
					cp[w].push_back(htw[*it]);
				}
			}
		}
		for (int w : in){
			auto it = hs.upper_bound(y[w]);
			if (it != hs.end()) cp[w+m].push_back(htw[*it]);
			if (it != hs.begin()){
				it--;
				if (*it == y[w] && it != hs.begin()){
					it--;
					cp[w+m].push_back(htw[*it]);
				}
			}
		}
	}
	map<ll,vector<pair<ll,ll>>> gh;
	for (int i=0; i<m; i++){
		ip[i].push_back(l[i]);
		ip[i].push_back(r[i]);
		for (int next : cp[i]){
			if (y[next] <= h[r[i]]) ip[next].push_back(r[i]);
		}
		for (int next : cp[i+m]){
			if (y[next] <= h[l[i]]) ip[next].push_back(l[i]);
		}
	}
	for (int i=0; i<m; i++){
		if (l[i] <= s && s <= r[i] && y[i] <= h[s]) gh[hf(s, 0)].push_back({hf(s, y[i]), y[i]});
		if (l[i] <= g && g <= r[i] && y[i] <= h[g]) gh[hf(g, y[i])].push_back({hf(g, 0), y[i]});
		sort(ip[i].begin(), ip[i].end());
		for (int j=0; j+1<(int)ip[i].size(); j++){
			gh[hf(ip[i][j], y[i])].push_back({hf(ip[i][j+1], y[i]), x[ip[i][j+1]]-x[ip[i][j]]});
			gh[hf(ip[i][j+1], y[i])].push_back({hf(ip[i][j], y[i]), x[ip[i][j+1]]-x[ip[i][j]]});
		}
		for (int next : cp[i]){
			if (y[next] > h[r[i]]) continue;
			gh[hf(r[i], y[i])].push_back({hf(r[i], y[next]), abs(y[next]-y[i])});
			gh[hf(r[i], y[next])].push_back({hf(r[i], y[i]), abs(y[next]-y[i])});
		}
		/*for (int next : cp[i+m]){
			if (y[next] > h[l[i]]) continue;
			gh[hf(l[i], y[i])].push_back({hf(l[i], y[next]), abs(y[next]-y[i])});
			gh[hf(l[i], y[next])].push_back({hf(l[i], y[i]), abs(y[next]-y[i])});
		}*/
	}
	priority_queue<pair<ll,ll>> pq;
	pq.push({0, hf(s, 0)});
	unordered_set<ll> seen;
	while (!pq.empty()){
		ll cur = pq.top().second, d = -pq.top().first;
		pq.pop();
		if (seen.find(cur) != seen.end()) continue;
		seen.insert(cur);
		if (cur == hf(g, 0)) return d;
		for (pair<ll,ll> next : gh[cur]) pq.push({-(d+next.second), next.first});
	}
	return -1;
}

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