Submission #299506

#	Time	Username	Problem	Language	Result	Execution time	Memory
299506		TMJN	Sky Walking (IOI19_walk)	C++17	10 / 100	4097 ms	515192 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]);
	}
	for(int i=0;i<M;i++){
		for(int j=l[i];j<=r[i];j++){
			if(h[j]>=y[i]){
				node[j].push_back(y[i]);
			}
		}
	}
	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]});
		}
	}
	for(int i=0;i<M;i++){
		vector<pair<int,int>>p;
		for(int j=l[i];j<=r[i];j++){
			if(h[j]>=y[i]){
				p.push_back({j,lower_bound(node[j].begin(),node[j].end(),y[i])-node[j].begin()});
			}
		}
		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:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int j=0;j<node[i].size()-1;j++){
      |               ~^~~~~~~~~~~~~~~~~
walk.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int j=0;j<p.size()-1;j++){
      |               ~^~~~~~~~~~~

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