oj.uz

Submission #1047672

# Submission time Handle Problem Language Result Execution time Memory
1047672 2024-08-07T14:54:14 Z Alihan_8 Sky Walking (IOI19_walk) C++17
33 / 100
 866 ms 108228 KB 
#include "walk.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define ln '\n'

using i64 = long long;

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

const i64 inf = 1e15;

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) {
	{ // modification
		auto modify = [&](int u){
			int m = l.size();
			
			set <int> st;
			
			for ( int i = 0; i < m; i++ ){
				if ( y[i] <= h[u] && l[i] <= u && r[i] >= u ){
					l.pb(l[i]), r.pb(u); y.pb(y[i]);
					l.pb(u), r.pb(r[i]); y.pb(y[i]);
					st.insert(i);
				} 
			}
		};
		
		modify(s), modify(g);
	}
	
	int n = x.size(), m = l.size();
	
	vector <vector<ar<int,3>>> H(n);
	
	vector <vector<int>> qry(n);
	
	for ( int i = 0; i < m; i++ ){
		H[l[i]].pb({1, y[i], i});
		H[r[i]].pb({0, y[i], i});
		qry[r[i]].pb(i);
	}
	
	y.pb(0), l.pb(s), r.pb(s); // start
	y.pb(0), l.pb(g), r.pb(g); // end
	
	qry[s].pb(m), qry[g].pb(m + 1);
	
	vector <int> D(m + 2, -1), U(m + 2, -1);
	
	// m -> (0), m + 1 -> (n - 1)
	
	set <pair<int,int>> st;
	
	for ( int i = 0; i < n; i++ ){
		for ( auto &[t, u, j]: H[i] ){
			if ( t > 0 ){
				st.insert({u, j});
			} else if ( i + 1 < n ){ // for (n - 1, 0)
				st.erase({u, j});
			}
		}
		
		for ( auto &j: qry[i] ){
			auto it = st.lower_bound({y[j], -1});
			
			if ( it != st.end() ){
				U[j] = it -> second;
			}
			
			if ( it != st.begin() ){
				D[j] = prev(it) -> second;
			}
		}
	}
	
	//~ cout << "Up & Down : \n";
	//~ for ( int i = 0; i < m + 2; i++ ){
		//~ cout << U[i] << " " << D[i] << ln;
	//~ } cout << ln;
	
	vector <vector<int>> rng(m + 2);
	
	for ( int i = 0; i < m + 2; i++ ){
		rng[i].pb(l[i]);
		rng[i].pb(r[i]);
		
		if ( U[i] == i ) U[i] = -1;
		if ( D[i] == i ) D[i] = -1;
		
		if ( U[i] != -1 ){
			rng[U[i]].pb(r[i]);
		}
		
		if ( D[i] != -1 ){
			rng[D[i]].pb(r[i]);
		}
	}
	
	map <ar<int,2>,int> id;
	
	vector <vector<ar<i64,2>>> adj;
	
	int k = 0;
	
	auto get = [&](int u, int v){
		if ( !id.count({u, v}) ){
			id[{u, v}] = k++;
			adj.pb(vector <ar<i64,2>>());
		}
		
		return id[{u, v}];
	};
	
	for ( int i = 0; i < m + 2; i++ ){
		auto &p = rng[i];
		
		sort(all(p));
		p.resize(unique(all(p)) - p.begin());
		
		{ // assigning index
			for ( auto x: p ) get(x, y[i]); 
		}
		
		for ( int j = 0; j + 1 < (int)p.size(); j++ ){
			int u = get(p[j], y[i]), v = get(p[j + 1], y[i]);
			
			adj[u].pb({v, x[p[j + 1]] - x[p[j]]}); // to the right
			adj[v].pb({u, x[p[j + 1]] - x[p[j]]});
			
			//~ cout << "{" << p[j] << " " << y[i] << "}  {" << p[j + 1] << " " << y[i] << "}  " << x[p[j + 1]] - x[p[j]] << ln;
		}
		
		if ( D[i] != -1 ){ // down
			int u = get(r[i], y[i]), v = get(r[i], y[D[i]]);
			
			//~ cout << "{" << r[i] << " " << y[i] << "}  {" << r[i] << " " << y[D[i]] << "}  " << y[i] - y[D[i]] << ln; 
			
			adj[u].pb({v, y[i] - y[D[i]]});
			adj[v].pb({u, y[i] - y[D[i]]});
		} 
		
		if ( U[i] != -1 ){ // up
			int u = get(r[i], y[i]), v = get(r[i], y[U[i]]);
			
			//~ cout << "{" << r[i] << " " << y[i] << "}  {" << r[i] << " " << y[U[i]] << "}  " << -y[i] + y[U[i]] << ln; 
			
			adj[u].pb({v, -y[i] + y[U[i]]});
			adj[v].pb({u, -y[i] + y[U[i]]});
		}
	}
	
	vector <i64> dp(k, inf);
	
	priority_queue <ar<i64,2>> q;
	
	int u = get(s, 0);
	
	dp[u] = 0;
	q.push({0, u});
	
	while ( !q.empty() ){
		auto [val, u] = q.top();
		q.pop();
		
		if ( -val != dp[u] ) continue;
		
		for ( auto &[v, w]: adj[u] ){
			if ( chmin(dp[v], dp[u] + w) ){
				q.push({-dp[v], v});
			}
		}
	}
	
	u = get(g, 0);
	
	if ( dp[u] == inf ){
		dp[u] = -1;
	}
	
	return dp[u];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 436 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 530 ms 69960 KB Output is correct
4 Correct 485 ms 77684 KB Output is correct
5 Incorrect 410 ms 62872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 21448 KB Output is correct
2 Correct 727 ms 80196 KB Output is correct
3 Correct 715 ms 82532 KB Output is correct
4 Correct 785 ms 93092 KB Output is correct
5 Correct 814 ms 94992 KB Output is correct
6 Correct 777 ms 100256 KB Output is correct
7 Correct 308 ms 52324 KB Output is correct
8 Correct 285 ms 55328 KB Output is correct
9 Correct 866 ms 108228 KB Output is correct
10 Correct 418 ms 78868 KB Output is correct
11 Correct 7 ms 4184 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 21448 KB Output is correct
2 Correct 727 ms 80196 KB Output is correct
3 Correct 715 ms 82532 KB Output is correct
4 Correct 785 ms 93092 KB Output is correct
5 Correct 814 ms 94992 KB Output is correct
6 Correct 777 ms 100256 KB Output is correct
7 Correct 308 ms 52324 KB Output is correct
8 Correct 285 ms 55328 KB Output is correct
9 Correct 866 ms 108228 KB Output is correct
10 Correct 418 ms 78868 KB Output is correct
11 Correct 7 ms 4184 KB Output is correct
12 Correct 752 ms 83304 KB Output is correct
13 Correct 668 ms 91812 KB Output is correct
14 Correct 834 ms 94328 KB Output is correct
15 Correct 509 ms 77984 KB Output is correct
16 Correct 544 ms 80472 KB Output is correct
17 Correct 665 ms 93092 KB Output is correct
18 Correct 534 ms 76452 KB Output is correct
19 Correct 532 ms 80904 KB Output is correct
20 Correct 314 ms 52588 KB Output is correct
21 Correct 24 ms 9560 KB Output is correct
22 Correct 498 ms 71824 KB Output is correct
23 Correct 454 ms 71192 KB Output is correct
24 Correct 374 ms 62096 KB Output is correct
25 Correct 438 ms 69532 KB Output is correct
26 Correct 376 ms 61996 KB Output is correct
27 Correct 785 ms 95140 KB Output is correct
28 Correct 617 ms 91216 KB Output is correct
29 Correct 772 ms 101296 KB Output is correct
30 Correct 313 ms 51812 KB Output is correct
31 Correct 761 ms 108204 KB Output is correct
32 Correct 373 ms 64940 KB Output is correct
33 Correct 338 ms 63400 KB Output is correct
34 Correct 442 ms 79272 KB Output is correct
35 Correct 405 ms 70568 KB Output is correct
36 Correct 351 ms 59296 KB Output is correct
37 Correct 283 ms 53160 KB Output is correct
38 Correct 380 ms 66240 KB Output is correct
39 Correct 583 ms 97412 KB Output is correct
40 Correct 351 ms 62376 KB Output is correct
41 Correct 320 ms 57016 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 436 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -