oj.uz

Submission #795919

# Submission time Handle Problem Language Result Execution time Memory
795919 2023-07-27T22:17:40 Z APROHACK Sky Walking (IOI19_walk) C++17
0 / 100
 2588 ms 999128 KB 
#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>llersecciones;
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 generatellerseccion(ll build, ll y){
	if(llersecciones.count({buildings[build].ff, y}))return llersecciones[{buildings[build].ff, y}];
	corresponde.pb({buildings[build].ff, y});
	puntosEnB[build].pb({buildings[build].ff, y});
	llersecciones[{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 = generatellerseccion(l, y), actual;
	ll antX = buildings[l].ff;
	for(ll i = l+1 ; i <= r ; i ++){
		if(buildings[i].ss >= y){
			actual = generatellerseccion(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)return distancias[g];
		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});
			}
		}
	}
	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 ++){
		generatellerseccion(i, 0);
		//puntosEnB[i].pb({x[i], 0});
		//llersecciones[{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(llersecciones[puntosEnB[i][j-1]], llersecciones[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(llersecciones[{x[s], 0}], llersecciones[{x[g], 0}]);
}

Compilation message

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:95: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]
   95 |   for (ll j = 1 ; j < puntosEnB[i].size() ; j ++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73056 KB Output is correct
2 Correct 35 ms 73008 KB Output is correct
3 Correct 41 ms 72988 KB Output is correct
4 Incorrect 36 ms 73072 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 73048 KB Output is correct
2 Correct 39 ms 73008 KB Output is correct
3 Correct 1124 ms 239152 KB Output is correct
4 Correct 1169 ms 245852 KB Output is correct
5 Correct 869 ms 222632 KB Output is correct
6 Correct 1022 ms 204664 KB Output is correct
7 Incorrect 939 ms 222824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 89828 KB Output is correct
2 Runtime error 2588 ms 999128 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 89828 KB Output is correct
2 Runtime error 2588 ms 999128 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73056 KB Output is correct
2 Correct 35 ms 73008 KB Output is correct
3 Correct 41 ms 72988 KB Output is correct
4 Incorrect 36 ms 73072 KB Output isn't correct
5 Halted 0 ms 0 KB -