Submission #299508

#	Time	Username	Problem	Language	Result	Execution time	Memory
299508		TMJN	Sky Walking (IOI19_walk)	C++17	24 / 100	4077 ms	524720 KiB

walk

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


struct edge{
	int to_x,to_y;
	int dist;
};
vector<int>node[100000];
vector<vector<edge>>e[100000];
vector<long long>dist[100000];

long long min_distance(vector<int>x,vector<int>h,vector<int>l,vector<int>r,vector<int>y,int s,int g){
	int N,M;
	N=x.size();
	M=l.size();
	for(int i=0;i<N;i++){
		node[i].push_back(0);
		node[i].push_back(h[i]);
	}
	set<int>st;
	priority_queue<pair<int,pair<int,int>>>que;
	for(int i=0;i<N;i++){
		que.push({h[i],{1,i}});
	}
	for(int i=0;i<M;i++){
		que.push({y[i],{0,i}});
	}
	while(!que.empty()){
		int height,type,id;
		height=que.top().first;
		type=que.top().second.first;
		id=que.top().second.second;
		que.pop();
		if(type){
			st.insert(id);
		}
		else{
			auto it=st.lower_bound(l[id]);
			while(true){
				node[*it].push_back(y[id]);
				if(*it==r[id])break;
				it++;
			}
		}
	}
	for(int i=0;i<N;i++){
		sort(node[i].begin(),node[i].end());
		node[i].erase(unique(node[i].begin(),node[i].end()),node[i].end());
		dist[i]=vector<long long>(node[i].size(),-1);
		e[i]=vector<vector<edge>>(node[i].size());
		for(int j=0;j<node[i].size()-1;j++){
			e[i][j].push_back({i,j+1,node[i][j+1]-node[i][j]});
			e[i][j+1].push_back({i,j,node[i][j+1]-node[i][j]});
		}
	}
	st.clear();
	for(int i=0;i<N;i++){
		que.push({h[i],{1,i}});
	}
	for(int i=0;i<M;i++){
		que.push({y[i],{0,i}});
	}
	while(!que.empty()){
		int height,type,id;
		height=que.top().first;
		type=que.top().second.first;
		id=que.top().second.second;
		que.pop();
		if(type){
			st.insert(id);
		}
		else{
			auto it=st.lower_bound(l[id]);
			vector<pair<int,int>>p;
			while(true){
				p.push_back({*it,lower_bound(node[*it].begin(),node[*it].end(),y[id])-node[*it].begin()});
				if(*it==r[id])break;
				it++;
			}
			for(int j=0;j<p.size()-1;j++){
				e[p[j].first][p[j].second].push_back({p[j+1].first,p[j+1].second,x[p[j+1].first]-x[p[j].first]});
				e[p[j+1].first][p[j+1].second].push_back({p[j].first,p[j].second,x[p[j+1].first]-x[p[j].first]});
			
			}
		}
	}
	priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>>pq;
	pq.push({0,{s,0}});
	while(!pq.empty()){
		long long l;
		int px;
		int py;
		l=pq.top().first;
		px=pq.top().second.first;
		py=pq.top().second.second;
		pq.pop();
		if(dist[px][py]==-1){
			dist[px][py]=l;
			for(edge E:e[px][py]){
				pq.push({l+E.dist,{E.to_x,E.to_y}});
			}
		}
	}
	return dist[g][0];
}

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:31:7: warning: variable 'height' set but not used [-Wunused-but-set-variable]
   31 |   int height,type,id;
      |       ^~~~~~
walk.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j=0;j<node[i].size()-1;j++){
      |               ~^~~~~~~~~~~~~~~~~
walk.cpp:82: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]
   82 |    for(int j=0;j<p.size()-1;j++){
      |                ~^~~~~~~~~~~
walk.cpp:66:7: warning: variable 'height' set but not used [-Wunused-but-set-variable]
   66 |   int height,type,id;
      |       ^~~~~~

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