oj.uz

Submission #1043918

# Submission time Handle Problem Language Result Execution time Memory
1043918 2024-08-05T04:09:23 Z Alihan_8 Sky Walking (IOI19_walk) C++17
0 / 100
 383 ms 79048 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) {
	int n = x.size(), m = l.size();
	
	vector <vector<ar<int,3>>> H(n + 1);
	
	{ // shifting y
		y.pb(0);
		for ( int i = m; i > 0; i-- ){
			y[i] = y[i - 1];
		} y[0] = 0;
	}
	
	for ( int i = 1; i <= m; i++ ){
		H[l[i - 1]].pb({1, y[i], i});
		H[r[i - 1] + 1].pb({0, y[i], i});
	}
	
	set <pair<int,int>> st;
	
	vector <vector<int>> a(n, {0}), mp(m + 1);
	
	auto V = a;
	
	for ( int i = 0; i < n; i++ ){
		for ( auto &[t, y, j]: H[i] ){
			if ( t > 0 ){
				st.insert({y, j});
			} else st.erase({y, j});
		}
		
		auto it = st.begin();
		
		while ( it != st.end() && it -> first <= h[i] ){
			a[i].pb(it -> second);
			V[i].pb(it -> first);
			mp[it -> second].pb(i);
			it = next(it);
		}
	}
	
	vector <vector<i64>> dp(n);
	vector <vector<int>> id(n);
	
	for ( int i = 0; i < n; i++ ){
		sort(all(a[i]), [&](int &u, int &v){
			return y[u] < y[v];
		});
		
		sort(all(V[i]));
		
		int s = a[i].size();
		dp[i].resize(s, inf);
		id[i].resize(s);
		
		for ( int j = 1; j < s; j++ ){
			int x = a[i][j];
			
			id[i][j] = lower_bound(all(mp[x]), i) - mp[x].begin();
		}
	}
	
	dp[s][0] = 0;
	
	priority_queue <ar<i64,3>> q;
	
	q.push({0, s, 0});
	
	while ( !q.empty() ){
		auto [val, u, j] = q.top();
		q.pop();
		
		if ( -val != dp[u][j] ) continue;
		
		if ( j != 0 ){ // using skywalk j
			int t = a[u][j];
			
			for ( auto i: {id[u][j] - 1, id[u][j] + 1} ){
				
				if ( i < 0 || i >= (int)mp[t].size() ){
					continue;
				}
				
				int v = mp[t][i], nxt = lower_bound(all(V[v]), y[t]) - V[v].begin();
				
				if ( a[v][nxt] != t ){
					assert(false); return -2;
				}
				
				if ( chmin(dp[v][nxt], dp[u][j] + abs(x[v] - x[u])) ){
					q.push({-dp[v][nxt], v, nxt});
				}
			}
		}
		
		for ( auto i: {j + 1, j - 1} ){
			if ( i < 0 || i >= (int)dp[u].size() ){
				continue;
			}
			
			if ( chmin(dp[u][i], dp[u][j] + abs(y[a[u][j]] - y[a[u][i]])) ){
				q.push({-dp[u][i], u, i});
			}
		}
	}
	
	i64 ans = dp[g][0];
	
	if ( ans == inf ){
		ans = -1;
	}
	
	return ans;
}

Subtask #1
0 / 10.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 Runtime error 0 ms 604 KB Execution killed with signal 6
4 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 261 ms 32964 KB Output is correct
4 Correct 303 ms 51656 KB Output is correct
5 Correct 128 ms 46120 KB Output is correct
6 Correct 127 ms 44324 KB Output is correct
7 Correct 157 ms 46324 KB Output is correct
8 Correct 340 ms 38348 KB Output is correct
9 Correct 150 ms 44488 KB Output is correct
10 Correct 383 ms 60976 KB Output is correct
11 Correct 133 ms 28568 KB Output is correct
12 Correct 101 ms 37188 KB Output is correct
13 Correct 321 ms 56448 KB Output is correct
14 Correct 98 ms 36768 KB Output is correct
15 Runtime error 124 ms 79048 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 21396 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 21396 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.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 Runtime error 0 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -