Submission #612742

#	Time	Username	Problem	Language	Result	Execution time	Memory
612742		definitelynotmee	Sky Walking (IOI19_walk)	C++17	0 / 100	4070 ms	8032 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();

	

	bool ok = 1;
	for(int i = 1; i < n; i++){
		ok&=h[i] == h[i-1];
	}
	if(!ok){
		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];
	}

	matrix<pii> g(m+2);
	// g[m] -> 0, g[m+1]->n-1


	matrix<pii> op(n+1);

	for(int i = 0; i < m; i++){
		op[l[i]].push_back({1,i});
		op[r[i]+1].push_back({0,i});
		if(l[i] == 0)
			g[m].push_back({i,y[i]}), g[i].push_back({m,y[i]});
		if(r[i] == n-1)
			g[m+1].push_back({i,y[i]}), g[i].push_back({m+1,y[i]});
	}
	set<pii> s;

	for(int i = 0; i < n; i++){
		sort(all(op));
		for(auto [type,id]: op[i]){
			if(type){
				auto it = s.lower_bound({y[id],id});
				if(it != s.end()){
					g[it->ss].push_back({id,abs(y[id]-it->ff)});
					g[id].push_back({it->ss,abs(y[id]-it->ff)});
				}
				if(it!=s.begin()){
					it--;
					g[it->ss].push_back({id,abs(y[id]-it->ff)});
					g[id].push_back({it->ss,abs(y[id]-it->ff)});
				}
				s.insert({y[id],id});
			} else {
				s.erase({y[id],id});
			}
		}
	}

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

	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[m+1] == (1ll<<60))
		return -1;
	
	return dist[m+1]+x.back()-x[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:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int i = 0; i < adj.size(); i++){
      |                   ~~^~~~~~~~~~~~
walk.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int j = 0; j < adj.size(); j++){
      |                   ~~^~~~~~~~~~~~
walk.cpp:70:21: 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]
   70 |    for(int j = 1; j < i.size(); j++){
      |                   ~~^~~~~~~~~~

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