oj.uz

Submission #427568

# Submission time Handle Problem Language Result Execution time Memory
427568 2021-06-14T17:16:54 Z amoo_safar Sky Walking (IOI19_walk) C++17
15 / 100
 504 ms 33572 KB 
#include "walk.h"

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;

const int N = 1e5 + 10;

int n, m;
vector<int> x, h, l, r, y;

int Get_Max(int l, int r){ // [l, r]
	// cerr << ""
	if(r < l) return -1;
	return h[l];
	int mx = h[l];
	for(int i = l; i <= r; i++)
		mx = max(mx, h[i]);
	return mx;
}
vector<pii> G[N];
void Add_Edge(int a, int b){
	// cerr << "!! " << a << ' ' << b << '\n';
	int ls = max(l[a], l[b]);
	int rs = min(r[a], r[b]);
	if(max(y[a], y[b]) <= Get_Max(ls, rs)){
		G[a].pb({b, abs(y[a] - y[b])});
		G[b].pb({a, abs(y[a] - y[b])});
	}
	// cerr << "!! " << a << ' ' << b << '\n';
}

vector<int> ins[N], dl[N];
void Add(vector<int> sg){
	for(int i = 0; i < N; i++) ins[i].clear(), dl[i].clear();
	for(int i : sg){
		ins[l[i]].pb(i);
		dl[r[i]].pb(i);
	}
	set< pair<int, int> > st; // y id

	for(int i = 0; i < N; i++){
		// cerr << "^^ " << i << '\n';	
		for(auto u : ins[i]){
			// cerr << "&& " << u << ' ' << y[u] << '\n';
			st.insert({y[u], u});
			auto it = st.find({y[u], u});
			if(it != st.begin())
				Add_Edge(it->S, prev(it) -> S);
			if(next(it) != st.end())
				Add_Edge(it->S, next(it) -> S);
		}
		// cerr << "^^ " << i << '\n';
		for(auto u : dl[i]){
			auto it = st.find({y[u], u});
			if(it != st.begin() && next(it) != st.end())
				Add_Edge(next(it) -> S, prev(it) -> S);
			st.erase(it);
		}
	}
}

ll dis[N];
typedef pair<ll, ll> pll;
ll Djik(int src, int des){
	memset(dis, 31, sizeof dis);
	dis[src] = 0;
	set<pll> st;
	st.insert({dis[src], src});
	while(!st.empty()){
		int fr = st.begin() -> S;
		st.erase(st.begin());
		for(auto [adj, w] : G[fr]){
			if(dis[adj] > dis[fr] + w){
				st.erase({dis[adj], adj});
				dis[adj] = dis[fr] + w;
				st.insert({dis[adj], adj});
			}
		}
	}
	return dis[des];
}

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int s, int g) {
	if(s > g) swap(s, g);
	x = _x;
	h = _h;

	ll ans = x[g] - x[s];
	
	_l.pb(s); _r.pb(s); _y.pb(0);
	_l.pb(g); _r.pb(g); _y.pb(0);
	
	int src = _l.size() - 2;
	int des = _r.size() - 1;

	n = _x.size();
	m = _l.size();
	
	l = _l;
	r = _r;
	y = _y;

	vector<int> lft, mid, rgt;
	for(int i = 0; i < m; i++) mid.pb(i);

	// debug("A");
	Add(lft);
	// debug("B");
	Add(mid);
	// debug("C");
	Add(rgt);
	// debug("D");

	ans += Djik(src, des);
	int max_len = 1000000000;
	return ans > 1ll * (n + m) * max_len ? -1 : ans;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8012 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 78 ms 15868 KB Output is correct
2 Correct 266 ms 23268 KB Output is correct
3 Correct 274 ms 24284 KB Output is correct
4 Correct 337 ms 30736 KB Output is correct
5 Correct 492 ms 31920 KB Output is correct
6 Correct 415 ms 32060 KB Output is correct
7 Correct 173 ms 22496 KB Output is correct
8 Correct 256 ms 28220 KB Output is correct
9 Correct 432 ms 33572 KB Output is correct
10 Correct 289 ms 31660 KB Output is correct
11 Correct 20 ms 10040 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15868 KB Output is correct
2 Correct 266 ms 23268 KB Output is correct
3 Correct 274 ms 24284 KB Output is correct
4 Correct 337 ms 30736 KB Output is correct
5 Correct 492 ms 31920 KB Output is correct
6 Correct 415 ms 32060 KB Output is correct
7 Correct 173 ms 22496 KB Output is correct
8 Correct 256 ms 28220 KB Output is correct
9 Correct 432 ms 33572 KB Output is correct
10 Correct 289 ms 31660 KB Output is correct
11 Correct 20 ms 10040 KB Output is correct
12 Correct 255 ms 24068 KB Output is correct
13 Correct 293 ms 30580 KB Output is correct
14 Correct 474 ms 31876 KB Output is correct
15 Correct 288 ms 29168 KB Output is correct
16 Correct 279 ms 33272 KB Output is correct
17 Correct 281 ms 31088 KB Output is correct
18 Correct 278 ms 29084 KB Output is correct
19 Correct 316 ms 33248 KB Output is correct
20 Correct 175 ms 22380 KB Output is correct
21 Correct 42 ms 12620 KB Output is correct
22 Correct 169 ms 26548 KB Output is correct
23 Correct 172 ms 26664 KB Output is correct
24 Correct 210 ms 25204 KB Output is correct
25 Correct 169 ms 26208 KB Output is correct
26 Correct 163 ms 25836 KB Output is correct
27 Correct 504 ms 32284 KB Output is correct
28 Correct 218 ms 30348 KB Output is correct
29 Correct 486 ms 31928 KB Output is correct
30 Correct 139 ms 22380 KB Output is correct
31 Correct 468 ms 33452 KB Output is correct
32 Correct 200 ms 28460 KB Output is correct
33 Incorrect 182 ms 29112 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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