oj.uz

Submission #803069

# Submission time Handle Problem Language Result Execution time Memory
803069 2023-08-02T21:05:25 Z APROHACK Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 1018544 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>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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 73044 KB Output is correct
2 Correct 33 ms 73000 KB Output is correct
3 Correct 35 ms 73036 KB Output is correct
4 Correct 34 ms 73076 KB Output is correct
5 Correct 34 ms 73228 KB Output is correct
6 Correct 33 ms 73192 KB Output is correct
7 Correct 34 ms 73172 KB Output is correct
8 Correct 34 ms 73096 KB Output is correct
9 Correct 33 ms 73056 KB Output is correct
10 Correct 34 ms 73240 KB Output is correct
11 Correct 34 ms 73104 KB Output is correct
12 Correct 34 ms 73044 KB Output is correct
13 Correct 34 ms 73076 KB Output is correct
14 Correct 35 ms 73000 KB Output is correct
15 Correct 34 ms 72988 KB Output is correct
16 Correct 37 ms 73088 KB Output is correct
17 Correct 41 ms 73232 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 72976 KB Output is correct
2 Correct 41 ms 73052 KB Output is correct
3 Correct 904 ms 241244 KB Output is correct
4 Correct 1113 ms 248704 KB Output is correct
5 Correct 826 ms 225428 KB Output is correct
6 Correct 986 ms 207484 KB Output is correct
7 Correct 800 ms 225872 KB Output is correct
8 Correct 1150 ms 287376 KB Output is correct
9 Correct 838 ms 223788 KB Output is correct
10 Correct 1513 ms 318192 KB Output is correct
11 Correct 515 ms 162060 KB Output is correct
12 Correct 383 ms 134492 KB Output is correct
13 Correct 1337 ms 286876 KB Output is correct
14 Correct 1608 ms 132008 KB Output is correct
15 Correct 1048 ms 134552 KB Output is correct
16 Correct 450 ms 135444 KB Output is correct
17 Correct 470 ms 133184 KB Output is correct
18 Execution timed out 4078 ms 114316 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 90504 KB Output is correct
2 Runtime error 2329 ms 1018544 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 121 ms 90504 KB Output is correct
2 Runtime error 2329 ms 1018544 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 33 ms 73044 KB Output is correct
2 Correct 33 ms 73000 KB Output is correct
3 Correct 35 ms 73036 KB Output is correct
4 Correct 34 ms 73076 KB Output is correct
5 Correct 34 ms 73228 KB Output is correct
6 Correct 33 ms 73192 KB Output is correct
7 Correct 34 ms 73172 KB Output is correct
8 Correct 34 ms 73096 KB Output is correct
9 Correct 33 ms 73056 KB Output is correct
10 Correct 34 ms 73240 KB Output is correct
11 Correct 34 ms 73104 KB Output is correct
12 Correct 34 ms 73044 KB Output is correct
13 Correct 34 ms 73076 KB Output is correct
14 Correct 35 ms 73000 KB Output is correct
15 Correct 34 ms 72988 KB Output is correct
16 Correct 37 ms 73088 KB Output is correct
17 Correct 41 ms 73232 KB Output is correct
18 Correct 34 ms 72976 KB Output is correct
19 Correct 41 ms 73052 KB Output is correct
20 Correct 904 ms 241244 KB Output is correct
21 Correct 1113 ms 248704 KB Output is correct
22 Correct 826 ms 225428 KB Output is correct
23 Correct 986 ms 207484 KB Output is correct
24 Correct 800 ms 225872 KB Output is correct
25 Correct 1150 ms 287376 KB Output is correct
26 Correct 838 ms 223788 KB Output is correct
27 Correct 1513 ms 318192 KB Output is correct
28 Correct 515 ms 162060 KB Output is correct
29 Correct 383 ms 134492 KB Output is correct
30 Correct 1337 ms 286876 KB Output is correct
31 Correct 1608 ms 132008 KB Output is correct
32 Correct 1048 ms 134552 KB Output is correct
33 Correct 450 ms 135444 KB Output is correct
34 Correct 470 ms 133184 KB Output is correct
35 Execution timed out 4078 ms 114316 KB Time limit exceeded
36 Halted 0 ms 0 KB -