Submission #171869

#	Time	Username	Problem	Language	Result	Execution time	Memory
171869		dsjong	Sky Walking (IOI19_walk)	C++14	24 / 100	2281 ms	227084 KiB

walk

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

unordered_map<long long,int> mp;
vector<pair<int,int>>adj[1000005];
long long dis[1000005];
long long INF=LONG_LONG_MAX;
bool vis[1000005];
void dijkstra(int source){
	class prioritize{
		public: bool operator ()(pair<int,long long>&p1 ,pair<int,long long>&p2){
			return p1.second>p2.second;
		}
	};
	for(int i=0;i<=1000000;i++) dis[i]=INF;
	priority_queue<pair<int,long long>,vector<pair<int,long long>>,prioritize>pq;
	dis[source]=0;
	pq.push({source,0});
	while(!pq.empty()){
		pair<int,long long>curr=pq.top();
		pq.pop();
		int cv=curr.first;
		long long cw=curr.second;
		if(vis[cv]) continue;
		vis[cv]=true; 
		for(auto i:adj[cv]){
			if(vis[i.first]) continue;
			if(i.second+cw<dis[i.first]){
				dis[i.first]=i.second+cw;
				//cout<<i.first<<" "<<dis[i.first]<<endl;
				pq.push({i.first,dis[i.first]});
			}
		}
	}
}
long long get(int x, int y){
	return (x*(1e9+1ll)+y);
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, std::vector<int> y, int s, int g) {
	vector<pair<int,int>>all;
	vector<pair<int,pair<int,int>>>v;
	int n = x.size(), m = l.size();
	for(int i=0;i<m;i++){
		v.push_back({y[i],{l[i],r[i]}});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<m;i++){
		y[i]=v[i].first;
		l[i]=v[i].second.first;
		r[i]=v[i].second.second;
	}
	set<int>se;
	for(int i=0;i<n;i++) se.insert(i);
	mp[get(s,0)]=0;
	mp[get(g,0)]=1;
	int cnt = 2;
	all.push_back({s,0});
	all.push_back({g,0});
	for(int i=0;i<m;i++){
		//cout<<y[i]<<" "<<l[i]<<" "<<r[i]<<": ";
		int last=-1, cur=0;
		while(cur<r[i]){
			auto it=se.lower_bound(max(last+1,l[i]));
			if(it==se.end()) break;
			cur=*it;
			if(h[cur]>=y[i]){
				all.push_back({cur,y[i]});
				//cout<<cur<<" "<<y[i]<<endl;
				if(!mp[get(cur,y[i])]) mp[get(cur,y[i])]=cnt++;
				if(last!=-1){
					adj[mp[get(cur,y[i])]].push_back({mp[get(last,y[i])],x[cur]-x[last]});
					adj[mp[get(last,y[i])]].push_back({mp[get(cur,y[i])],x[cur]-x[last]});
				}
				last=cur;
			}
			else{
				se.erase(it);
			}
		}
	}
	/*for(int i = 0; i < m; i++){
		int last=-1;
		for(int j = l[i]; j <= r[i]; j++){
			if(!mp[get(j, y[i])] && h[j] >= y[i]){
				all.push_back({j, y[i]});
				mp[get(j, y[i])] =cnt;
				//cout<<mp[{j,y[i]}]<<endl;
				cnt++;
			}
			if(h[j]>=y[i]){
				if(last!=-1){
					adj[mp[get(j,y[i])]].push_back({mp[get(last,y[i])],x[j]-x[last]});
					adj[mp[get(last,y[i])]].push_back({mp[get(j,y[i])],x[j]-x[last]});
					//cout<<mp[{j,y[i]}]<<" "<<mp[{last,y[i]}]<<" "<<x[j]-x[last]<<endl;
				}
				last = j;
			}
		}
	}*/
	sort(all.begin(),all.end());
	for(int i=1; i < all.size(); i++){
		if(all[i].first == all[i-1].first){
			adj[mp[get(all[i].first,all[i].second)]].push_back({mp[get(all[i-1].first,all[i-1].second)], all[i].second-all[i-1].second});
			adj[mp[get(all[i-1].first,all[i-1].second)]].push_back({mp[get(all[i].first,all[i].second)], all[i].second-all[i-1].second});
		}
	}
	dijkstra(0);
	if(dis[1]==INF) return -1;
	return dis[1];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i < all.size(); i++){
               ~~^~~~~~~~~~~~

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