Submission #612723

#	Time	Username	Problem	Language	Result	Execution time	Memory
612723		definitelynotmee	Sky Walking (IOI19_walk)	C++17	24 / 100	3085 ms	1048576 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

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 from, int to) {
	int n = x.size();
	int m = l.size();

	int nodes = n;

	matrix<pii> lines;
	for(int i = 0; i < n; i++)
		lines.push_back({{0,i}});
	set<int> s;

	vector<int> obuild(n), oline(m);
	iota(all(obuild),0);
	iota(all(oline),0);

	sort(all(obuild),[&](int a, int b){
		return h[a] > h[b];
	});
	sort(all(oline),[&](int a, int b){
		return y[a] > y[b];
	});

	int ptr = 0;

	for(int i : oline){
		while(ptr < n && h[obuild[ptr]] >= y[i])
			s.insert(obuild[ptr]), ptr++;
		vector<int> adj;

		auto it = s.lower_bound(l[i]);
		while(it!=s.end() && *it <= r[i])
			adj.push_back(*it), it++;
		
		vector<pii> hor;
		for(int i = 0; i < adj.size(); i++){
			hor.push_back({x[adj[i]],nodes+i});
		}
		lines.push_back(hor);

		for(int j = 0; j < adj.size(); j++){
			//cout << nodes+j << " = " << "(" << x[adj[j]] << ',' << y[i] << ")\n";
			lines[adj[j]].push_back({y[i],nodes+j});
		}

		nodes+=adj.size();
	}

	matrix<pii> g(nodes);

	for(auto& i : lines){
		sort(all(i));
		for(int j = 1; j < i.size(); j++){
			int peso = i[j].ff-i[j-1].ff;
			g[i[j-1].ss].push_back({i[j].ss,peso});
			g[i[j].ss].push_back({i[j-1].ss,peso});
		}
	}

	vector<ll> dist(nodes,1ll<<60);
	dist[from] = 0;
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	pq.push({0,from});

	while(!pq.empty()){
		int cur = pq.top().ss;
		int curp = pq.top().ff;
		pq.pop();
		if(curp > dist[cur])
			continue;
		for(auto [viz,peso] : g[cur]){
			if(dist[viz] > dist[cur]+peso){
				dist[viz] = dist[cur]+peso;
				pq.push({dist[viz],viz});
			}
		}
	}
	// for(int i = 0; i < nodes; i++)
	// 	cout << "->" << i << ": " << dist[i] << '\n';
	if(dist[to] == (1ll<<60))
		return -1;
	
	return dist[to];
}

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:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < adj.size(); i++){
      |                  ~~^~~~~~~~~~~~
walk.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int j = 0; j < adj.size(); j++){
      |                  ~~^~~~~~~~~~~~
walk.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j = 1; j < i.size(); j++){
      |                  ~~^~~~~~~~~~

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