제출 #1071633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071633		pcc	Sky Walking (IOI19_walk)	C++17	24 / 100	1117 ms	193448 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define _all(T) T.begin(),T.end()
#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>

const int mxn = 2e6+10;
const ll inf = 1e18;

vector<pii> paths[mxn];
ll dist[mxn];
int N;

vector<pii> pts;
set<int> st;
vector<pii> op;

namespace DIJKSTRA{
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	bitset<mxn> vis;
	void GO(){
		vis.reset();
		for(int i = 0;i<pts.size();i++)pq.push(pll(dist[i],i));
		while(!pq.empty()){
			auto [d,now] = pq.top();
			pq.pop();
			if(vis[now])continue;
			vis[now] = true;
			for(auto [nxt,w]:paths[now]){
				if(vis[nxt]||d+w>=dist[nxt])continue;
				dist[nxt] = d+w;
				pq.push(pll(d+w,nxt));
			}
		}
		return;
	}
}

long long min_distance(std::vector<int32_t> x, std::vector<int32_t> H, std::vector<int32_t> l, std::vector<int32_t> r, std::vector<int32_t> y, int32_t s, int32_t ed) {
	N = x.size();
	for(int i = 0;i<N;i++){
		op.push_back(pii(H[i],i));
	}
	for(int i = 0;i<l.size();i++){
		op.push_back(pii(y[i],-i-1));
	}
	sort(op.rbegin(),op.rend());

	for(auto [h,id]:op){
		if(id>=0){
			pts.push_back(pii(id,h));
			st.insert(id);
		}
		else{
			id = -id;
			id--;
			auto lit = st.lower_bound(l[id]);
			auto rit = st.upper_bound(r[id]);
			for(auto it = lit;it != rit;it++){
				pts.push_back(pii(*it,h));
			}
			id = -id;
		}
	}

	for(int i = 0;i<N;i++)pts.push_back(pii(i,0));
	sort(pts.begin(),pts.end());
	pts.resize(unique(pts.begin(),pts.end())-pts.begin());
	st.clear();

	for(auto [h,id]:op){
		if(id>=0){
			st.insert(id);
		}
		else{
			id = -id;
			id--;
			auto lit = st.find(l[id]);
			auto rit = st.upper_bound(r[id]);
			int pre = lower_bound(_all(pts),pii(*lit,h))-pts.begin();
			for(auto it = lit;it != rit;it++){
				int now = lower_bound(_all(pts),pii(*it,h))-pts.begin();
				if(it != lit){
					paths[now].push_back(pii(pre,x[*it]-x[*prev(it)]));
					paths[pre].push_back(pii(now,x[*it]-x[*prev(it)]));
				}
				pre = now;
			}
		}
	}

	for(int i = 1;i<pts.size();i++){
		if(pts[i].fs == pts[i-1].fs){
			paths[i].push_back(pii(i-1,pts[i].sc-pts[i-1].sc));
			paths[i-1].push_back(pii(i,pts[i].sc-pts[i-1].sc));
		}
	}

	fill(dist,dist+pts.size(),inf);
	s = lower_bound(pts.begin(),pts.end(),pii(s,0))-pts.begin();
	ed = lower_bound(pts.begin(),pts.end(),pii(ed,0))-pts.begin();
	dist[s] = 0;
	DIJKSTRA::GO();
	ll ans = dist[ed];
	return ans>=inf?-1:ans;
}

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'void DIJKSTRA::GO()':
walk.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i = 0;i<pts.size();i++)pq.push(pll(dist[i],i));
      |                 ~^~~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0;i<l.size();i++){
      |                ~^~~~~~~~~
walk.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 1;i<pts.size();i++){
      |                ~^~~~~~~~~~~

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