Submission #803069

#	Time	Username	Problem	Language	Result	Execution time	Memory
803069		APROHACK	Sky Walking (IOI19_walk)	C++17	10 / 100	4078 ms	1018544 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
struct skywalk{
	ll l, r, y;
};
vector<pair<ll, ll>>buildings;
vector<skywalk>skywalks;
map<pair<ll, ll>, ll>intersecciones;
vector<pair<ll, ll>>puntosEnB[100005]; // los puntos de cada building
// la memoria se podria optimizar.

ll puntoCur = 0;
vector<pair<ll, ll> >adj[3000000]; // distancia, nodo
int n, m;
vector<pair<ll, ll>>corresponde;

ll generateinterseccion(ll build, ll y){
	if(intersecciones.count({buildings[build].ff, y})==1)return intersecciones[{buildings[build].ff, y}];
	corresponde.pb({buildings[build].ff, y});
	puntosEnB[build].pb({buildings[build].ff, y});
	intersecciones[{buildings[build].ff, y}] = puntoCur ++;
	return puntoCur - 1;
}
void unir(ll a, ll b, ll distancia){
	distancia = abs(distancia);
	adj[a].pb({distancia, b});
	adj[b].pb({distancia, a});
}

void getI(ll l, ll r, ll y){
	ll anterior = generateinterseccion(l, y), actual;
	ll antX = buildings[l].ff;
	for(ll i = l+1 ; i <= r ; i ++){
		if(buildings[i].ss >= y){
			actual = generateinterseccion(i, y);
			unir(anterior, actual, buildings[i].ff - antX);
			anterior = actual;
			antX = buildings[i].ff;
		}
	}
}

ll dijkstra(ll s, ll g){
	priority_queue<pair<ll, ll>>pq;
	pq.push({0, s});
	ll distancias[puntoCur+1];
	for(ll i = 0 ; i < puntoCur ; i ++){
		distancias[i] = LLONG_MAX;
	}
	distancias[s] = 0;
	while(!pq.empty()){
		pair<ll, ll>cur = pq.top();
		pq.pop();
		cur.ff = -cur.ff;
		if(cur.ss == g)break;
		if(distancias[cur.ss] < cur.ff)continue;
		//cout << "arrived " << cur.ss << endl;
		for(ll i = 0 ; i < adj[cur.ss].size() ; i ++){
			auto nxt = adj[cur.ss][i];
			//cout << "can go " << corresponde[nxt.ss].ff << ", " << corresponde[nxt.ss].ss << endl;
			//cout << nxt.ff + cur.ff << " < " << distancias[nxt.ss] << endl; 
			if(nxt.ff + cur.ff < distancias[nxt.ss]){
				distancias[nxt.ss] = nxt.ff + cur.ff;
				pq.push({-distancias[nxt.ss], nxt.ss});
			}
		}
	}
	if(distancias[g] == LLONG_MAX)distancias[g] = -1;
	return distancias[g];
}

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) {
	n = x.size();
	m = l.size();
	for(ll i = 0 ; i < n ; i ++){
		buildings.pb({x[i], h[i]});
	}
	for(ll i = 0 ; i < m ; i ++){
		skywalks.pb({l[i], r[i], y[i]});
	}
	for(ll i = 0 ; i < n ; i ++){
		generateinterseccion(i, 0);
		//puntosEnB[i].pb({x[i], 0});
		//intersecciones[{x[i], 0}] = puntoCur++;
	}
	for(ll i = 0 ; i < m ; i++){
		getI(l[i], r[i], y[i]);
	}
	for(ll i = 0 ; i < n ; i ++){
		sort(puntosEnB[i].begin(), puntosEnB[i].end());
		for (ll j = 1 ; j < puntosEnB[i].size() ; j ++){
			unir(intersecciones[puntosEnB[i][j-1]], intersecciones[puntosEnB[i][j]], puntosEnB[i][j].ss - puntosEnB[i][j-1].ss);
		}
	}
	//for(ll i = 0 ; i < puntoCur ; i ++){
	//	cout << i << " = " << corresponde[i].ff << ", " << corresponde[i].ss << endl;
	//}
	return dijkstra(intersecciones[{x[s], 0}], intersecciones[{x[g], 0}]);
}

Compilation message (stderr)

walk.cpp: In function 'long long int dijkstra(long long int, long long int)':
walk.cpp:63:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(ll i = 0 ; i < adj[cur.ss].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
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:96:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (ll j = 1 ; j < puntosEnB[i].size() ; j ++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

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