oj.uz

Submission #612708

# Submission time Handle Problem Language Result Execution time Memory
612708 2022-07-29T21:12:04 Z morete Sky Walking (IOI19_walk) C++17
33 / 100
 309 ms 31988 KB 
#include "bits/stdc++.h"
#include "walk.h"
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<tuple>
#include<algorithm>

using namespace std;

#define pb push_back
#define snd second
#define fst first

typedef long long int ll;

const ll INF = 9e18;

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) {
	int n, m;
	map<ll, ll> dst; // altura, custo vertical, barra horizontal
	map<ll, vector<ll>> com, fim;

	n = x.size();
	m = l.size();

	for (int i = 0; i < m; i++){ // altura tem que bater pelo enunciado
		com[x[l[i]]].push_back(y[i]);
		fim[x[r[i]]].push_back(y[i]); // sei onde começa e onde acaba
	}

	// tomar cuidado com inicio e fim na mesma altura na mesma barra

	ll ans = INF; //INF

	dst[0] = 0; // altura zero no inicio
	fim[x[0]].pb(0); // depois não é mais válido

	for (int i = 0; i < n; i++){
		set<int> stay;

		for (auto e : com[x[i]]){
			if (dst.count(e)) 
				stay.insert(e); // não apaga essa altura, pode manter o mesmo valor
			else{
				auto it = dst.lower_bound(e);
				auto dit = it;

				if (dit != dst.begin()) // se existe
					dit--;

				ll val = INF; //INF

				if ((it != dst.end())){ // caminho válido
					val = min(val, (*it).snd + abs((*it).fst - e));
				}

				if ((dit != dst.end())){ // caminho válido
					val = min(val, (*dit).snd + abs((*dit).fst - e));
				}

				dst[e] = val;
			}

		}

		if (i == n - 1){
			for (auto e : dst)
				ans = min(ans, e.fst + e.snd);
		} 
	
		for (auto e : fim[x[i]])
			if (!stay.count(e))
				dst.erase(e);

		// cout<<i<<" "<<x[i]<<endl;
		// for (auto e : dst)
		// 	cout<<e.fst<<" -- "<<e.snd<<endl;

		// cout<<"--------"<<endl<<endl;		

	}

	if (ans >= INF)
		return -1;

	return ans + (ll)((ll)x[n - 1] - (ll)x[0]);
}

// signed main(){
// 	int n, m;
// 	assert(2 == scanf("%d%d", &n, &m));
// 	vector<int> x(n), h(n);
// 	for (int i = 0; i < n; i++)
// 		assert(2 == scanf("%d%d", &x[i], &h[i]));
// 	vector<int> l(m), r(m), y(m);
// 	for (int i = 0; i < m; i++)
// 		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
// 	int s, g;
// 	assert(2 == scanf("%d%d", &s, &g));
// 	fclose(stdin);

// 	long long result = min_distance(x, h, l, r, y, s, g);

// 	printf("%lld\n", result);
// 	fclose(stdout);
// 	return 0;
// }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5052 KB Output is correct
2 Correct 88 ms 5320 KB Output is correct
3 Correct 121 ms 7616 KB Output is correct
4 Correct 295 ms 24436 KB Output is correct
5 Correct 279 ms 26756 KB Output is correct
6 Correct 309 ms 26424 KB Output is correct
7 Correct 142 ms 21492 KB Output is correct
8 Correct 212 ms 26072 KB Output is correct
9 Correct 299 ms 27972 KB Output is correct
10 Correct 175 ms 26876 KB Output is correct
11 Correct 25 ms 8852 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5052 KB Output is correct
2 Correct 88 ms 5320 KB Output is correct
3 Correct 121 ms 7616 KB Output is correct
4 Correct 295 ms 24436 KB Output is correct
5 Correct 279 ms 26756 KB Output is correct
6 Correct 309 ms 26424 KB Output is correct
7 Correct 142 ms 21492 KB Output is correct
8 Correct 212 ms 26072 KB Output is correct
9 Correct 299 ms 27972 KB Output is correct
10 Correct 175 ms 26876 KB Output is correct
11 Correct 25 ms 8852 KB Output is correct
12 Correct 126 ms 9692 KB Output is correct
13 Correct 270 ms 28376 KB Output is correct
14 Correct 274 ms 30756 KB Output is correct
15 Correct 232 ms 27852 KB Output is correct
16 Correct 226 ms 28092 KB Output is correct
17 Correct 250 ms 28088 KB Output is correct
18 Correct 230 ms 27944 KB Output is correct
19 Correct 231 ms 28068 KB Output is correct
20 Correct 150 ms 24600 KB Output is correct
21 Correct 60 ms 19532 KB Output is correct
22 Correct 196 ms 26284 KB Output is correct
23 Correct 187 ms 26564 KB Output is correct
24 Correct 189 ms 27184 KB Output is correct
25 Correct 180 ms 26396 KB Output is correct
26 Correct 206 ms 28236 KB Output is correct
27 Correct 308 ms 31484 KB Output is correct
28 Correct 242 ms 28084 KB Output is correct
29 Correct 292 ms 30396 KB Output is correct
30 Correct 144 ms 24488 KB Output is correct
31 Correct 298 ms 31988 KB Output is correct
32 Correct 169 ms 25780 KB Output is correct
33 Correct 182 ms 29740 KB Output is correct
34 Correct 189 ms 29076 KB Output is correct
35 Correct 207 ms 27400 KB Output is correct
36 Correct 201 ms 26448 KB Output is correct
37 Correct 184 ms 22908 KB Output is correct
38 Correct 205 ms 29232 KB Output is correct
39 Correct 239 ms 30880 KB Output is correct
40 Correct 200 ms 27392 KB Output is correct
41 Correct 188 ms 25168 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -