oj.uz

Submission #795917

# Submission time Handle Problem Language Result Execution time Memory
795917 2023-07-27T22:14:40 Z APROHACK Sky Walking (IOI19_walk) C++17
0 / 100
 2380 ms 923616 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{
	int l, r, y;
};
vector<pair<int, int>>buildings;
vector<skywalk>skywalks;
map<pair<int, int>, int>intersecciones;
vector<pair<int, int>>puntosEnB[100005]; // los puntos de cada building
// la memoria se podria optimizar.

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

int generateInterseccion(int build, int y){
	if(intersecciones.count({buildings[build].ff, y}))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(int a, int b, ll distancia){
	distancia = abs(distancia);
	adj[a].pb({distancia, b});
	adj[b].pb({distancia, a});
}

void getI(int l, int r, int y){
	ll anterior = generateInterseccion(l, y), actual;
	ll antX = buildings[l].ff;
	for(int 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(int s, int g){
	priority_queue<pair<ll, int>>pq;
	pq.push({0, s});
	ll distancias[puntoCur+1];
	for(int i = 0 ; i < puntoCur ; i ++){
		distancias[i] = LLONG_MAX;
	}
	distancias[s] = 0;
	while(!pq.empty()){
		pair<ll, int>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(int 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(int i = 0 ; i < n ; i ++){
		buildings.pb({x[i], h[i]});
	}
	for(int i = 0 ; i < m ; i ++){
		skywalks.pb({l[i], r[i], y[i]});
	}
	for(int i = 0 ; i < n ; i ++){
		generateInterseccion(i, 0);
		//puntosEnB[i].pb({x[i], 0});
		//intersecciones[{x[i], 0}] = puntoCur++;
	}
	for(int i = 0 ; i < m ; i++){
		getI(l[i], r[i], y[i]);
	}
	for(int i = 0 ; i < n ; i ++){
		sort(puntosEnB[i].begin(), puntosEnB[i].end());
		for (int 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(int 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(int, int)':
walk.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int 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:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for (int j = 1 ; j < puntosEnB[i].size() ; j ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73036 KB Output is correct
2 Correct 36 ms 73092 KB Output is correct
3 Correct 36 ms 73060 KB Output is correct
4 Incorrect 37 ms 73004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73032 KB Output is correct
2 Correct 36 ms 73092 KB Output is correct
3 Correct 1070 ms 223888 KB Output is correct
4 Correct 1073 ms 233208 KB Output is correct
5 Correct 769 ms 211660 KB Output is correct
6 Correct 913 ms 195560 KB Output is correct
7 Incorrect 771 ms 211832 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 87880 KB Output is correct
2 Runtime error 2380 ms 923616 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 87880 KB Output is correct
2 Runtime error 2380 ms 923616 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 73036 KB Output is correct
2 Correct 36 ms 73092 KB Output is correct
3 Correct 36 ms 73060 KB Output is correct
4 Incorrect 37 ms 73004 KB Output isn't correct
5 Halted 0 ms 0 KB -