Submission #416741

#	Time	Username	Problem	Language	Result	Execution time	Memory
416741		peuch	Sky Walking (IOI19_walk)	C++17	0 / 100	4062 ms	200152 KiB

walk

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

const long long MAXN = 1e5 + 10;
const long long INF = 1e18;

map<pair<long long, long long>, long long> node;
vector<long long> dist;
vector<bool> marc;
vector<vector<long long> > ar, wg;
long long cnt = -1;

struct event{
	long long l, r, h;
	event(long long _l = 0, long long _r = 0, long long _h = 0){
		l = _l, r = _r, h = _h;
	}
	bool operator < (event x) const {
		if(h == x.h) return r - l < x.l - x.r;
		return h > x.h;	
	}
};

vector<event> line;

void dijkstra(long long ini);

long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int S, int G) {
	for(long long i = 0; i < X.size(); i++)
		line.push_back(event(i, i, H[i]));
	for(long long i = 0; i < L.size(); i++)
		line.push_back(event(L[i], R[i], Y[i]));
	sort(line.begin(), line.end());
	vector<long long> last(X.size(), 0);
	set<long long> torres;
	for(long long i = 0; i < line.size(); i++){
		long long l = line[i].l, r = line[i].r, y = line[i].h;
		if(l == r) torres.insert(l);
		else{
			set<long long> :: iterator it = torres.lower_bound(l);
			if(node[make_pair(*it, y)] == 0) {
				node[make_pair(*it, y)] = ++cnt;
				ar.push_back(vector<long long>(0));
				wg.push_back(vector<long long>(0));
				dist.push_back(INF);
				marc.push_back(0);
				if(last[*it] != 0) {
					ar[node[make_pair(*it, y)]].push_back(node[make_pair(*it, last[*it])]);
					ar[node[make_pair(*it, last[*it])]].push_back(node[make_pair(*it, y)]);
					wg[node[make_pair(*it, y)]].push_back(abs(y - last[*it]));
					wg[node[make_pair(*it, last[*it])]].push_back(abs(y - last[*it]));
				}
				last[*it] = y;
			}
			long long ult = *it;
			it++;
			while(it != torres.end() && *it <= r){
				if(node[make_pair(*it, y)] == 0) {
					node[make_pair(*it, y)] = ++cnt;
					ar.push_back(vector<long long>(0));
					wg.push_back(vector<long long>(0));
					dist.push_back(INF);
					marc.push_back(0);
					if(last[*it] != 0) {
						ar[node[make_pair(*it, y)]].push_back(node[make_pair(*it, last[*it])]);
						ar[node[make_pair(*it, last[*it])]].push_back(node[make_pair(*it, y)]);
						wg[node[make_pair(*it, y)]].push_back(abs(y - last[*it]));
						wg[node[make_pair(*it, last[*it])]].push_back(abs(y - last[*it]));
					}
					last[*it] = y;
				}
				ar[node[make_pair(*it, y)]].push_back(node[make_pair(ult, y)]);
				ar[node[make_pair(ult, y)]].push_back(node[make_pair(*it, y)]);
				wg[node[make_pair(*it, y)]].push_back(abs(X[*it] - X[ult]));
				wg[node[make_pair(ult, y)]].push_back(abs(X[*it] - X[ult]));
				
				ult = *it;
				it++;
			}
		}
	}
	for(long long i = 0; i < X.size(); i++){
		if(node[make_pair(i, 0)] == 0) {
			node[make_pair(i, 0)] = ++cnt;
			ar.push_back(vector<long long>(0));
			wg.push_back(vector<long long>(0));	
			dist.push_back(INF);
			marc.push_back(0);
			if(last[i] != 0) {
				ar[node[make_pair(i, 0)]].push_back(node[make_pair(i, last[i])]);
				ar[node[make_pair(i, last[i])]].push_back(node[make_pair(i, 0)]);
				wg[node[make_pair(i, 0)]].push_back(abs(0 - last[i]));
				wg[node[make_pair(i, last[i])]].push_back(abs(0 - last[i]));			
			}
			last[i] = 0;
		}
	}
	dijkstra(node[make_pair(S, 0)]);
	if(dist[node[make_pair(G, 0)]] >= INF) dist[node[make_pair(G, 0)]] = -1;
	return dist[node[make_pair(G, 0)]];
}

void dijkstra(long long ini){
	dist[ini] = 0;
	set<pair<long long, long long> > s;
	for(long long i = 0; i <= cnt; i++)
		s.insert(make_pair(dist[i], i));
	while(!s.empty()){
		long long cur = s.begin()->second;
		if(dist[cur] >= INF) break;
		marc[cur] = 1;
		s.erase(s.begin());
		for(long long i = 0; i < ar[cur].size(); i++){
			long long viz = ar[cur][i];
			if(marc[viz]) continue;
			s.erase(make_pair(dist[viz], viz));
			dist[viz] = min(dist[viz], dist[cur] + wg[cur][i]);
			s.insert(make_pair(dist[viz], viz));
		}
	}
}

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:30:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(long long i = 0; i < X.size(); i++)
      |                       ~~^~~~~~~~~~
walk.cpp:32:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(long long i = 0; i < L.size(); i++)
      |                       ~~^~~~~~~~~~
walk.cpp:37:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(long long i = 0; i < line.size(); i++){
      |                       ~~^~~~~~~~~~~~~
walk.cpp:83:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(long long i = 0; i < X.size(); i++){
      |                       ~~^~~~~~~~~~
walk.cpp: In function 'void dijkstra(long long int)':
walk.cpp:114:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(long long i = 0; i < ar[cur].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~

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