oj.uz

Submission #622762

# Submission time Handle Problem Language Result Execution time Memory
622762 2022-08-04T14:15:39 Z cheissmart Sky Walking (IOI19_walk) C++14
33 / 100
 4000 ms 23248 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define MP make_pair
#define EB emplace_back
#define PB push_back
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;
const ll oo = 1e18;

vi asr[N], asl[N];
map<int, ll> dist[N];

ll brute(vi& x, vi& h, vi& l, vi& r, vi& y, int s, int g) {
	int n = SZ(x);
	int m = SZ(l);
	vi ys = y;
	ys.PB(0);
	auto get_edges = [&] (int i, int yy) {
		V<pair<pi, int>> res;
		for(int yyy:ys) if(yyy <= h[i]) {
			res.EB(pi(i, yyy), abs(yy - yyy));
		}
		for(int j = 0; j < m; j++) {
			if(y[j] == yy && l[j] <= i && i <= r[i]) {
				for(int k = l[j]; k <= r[j]; k++) if(yy <= h[k]) {
					res.EB(pi(k, yy), abs(x[i] - x[k]));
				}
			}
		}
		return res;
	};
	priority_queue<pair<ll, pi>, V<pair<ll, pi>>, greater<pair<ll, pi>>> pq;
	pq.push(MP(0, pi(s, 0)));
	dist[0][0] = 0;
	
	while(pq.size()) {
		auto[dd, state] = pq.top(); pq.pop();
		auto[i, yy] = state;
		if(dd > dist[i][yy]) continue;
		V<pair<pi, int>> res = get_edges(i, yy);
		for(auto[nstate, w]:res) {
			auto[ni, nyy] = nstate;
			if(dist[ni].count(nyy) == 0 || dd + w < dist[ni][nyy]) {
				dist[ni][nyy] = dd + w;
				pq.push(MP(dd + w, nstate));
			}
		}
	}

	if(dist[g].count(0))
		return dist[g][0];
	return -1;
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	int n = SZ(x);
	int m = SZ(l);
	if(s != 0 || g != n - 1) {
		return brute(x, h, l, r, y, s, g);
	}

	for(int i = 0; i < m; i++) {
		asl[l[i]].PB(y[i]);
		asr[r[i]].PB(y[i]);
	}
	map<int, ll> mp;
	mp[0] = 0;
	asr[0].PB(0);

	for(int i = 0; i < n; i++) {
		set<int> no;
		for(int yy:asl[i]) {
			no.insert(yy);
			auto it = mp.lower_bound(yy);
			ll d = oo;
			if(it != mp.end()) 
				d = min(d, it -> S + abs(yy - it -> F));
			if(it != mp.begin()) {
				it--;
				d = min(d, it -> S + abs(yy - it -> F));
			}
			mp[yy] = d;
		}
		if(i < n - 1) for(int yy:asr[i]) {
			if(no.count(yy)) continue;
			mp.erase(yy);
		}
		if(mp.empty()) return -1;
	}

	ll ans = oo;
	for(auto[yy, d]:mp)
		ans = min(ans, d + yy);
	return ans + x[n - 1] - x[0];
}

Compilation message

walk.cpp: In function 'll brute(vi&, vi&, vi&, vi&, vi&, int, int)':
walk.cpp:48:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |   auto[dd, state] = pq.top(); pq.pop();
      |       ^
walk.cpp:49:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   auto[i, yy] = state;
      |       ^
walk.cpp:52:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |   for(auto[nstate, w]:res) {
      |           ^
walk.cpp:53:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |    auto[ni, nyy] = nstate;
      |        ^
walk.cpp:25:6: warning: unused variable 'n' [-Wunused-variable]
   25 |  int n = SZ(x);
      |      ^
walk.cpp: In function 'll min_distance(vi, vi, vi, vi, vi, int, int)':
walk.cpp:103:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |  for(auto[yy, d]:mp)
      |          ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9684 KB Output is correct
2 Correct 7 ms 9656 KB Output is correct
3 Incorrect 7 ms 9600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Execution timed out 4075 ms 23248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 11852 KB Output is correct
2 Correct 100 ms 13428 KB Output is correct
3 Correct 178 ms 14096 KB Output is correct
4 Correct 153 ms 17880 KB Output is correct
5 Correct 174 ms 22276 KB Output is correct
6 Correct 240 ms 20096 KB Output is correct
7 Correct 76 ms 15316 KB Output is correct
8 Correct 156 ms 19812 KB Output is correct
9 Correct 149 ms 21576 KB Output is correct
10 Correct 124 ms 21464 KB Output is correct
11 Correct 15 ms 10452 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 11852 KB Output is correct
2 Correct 100 ms 13428 KB Output is correct
3 Correct 178 ms 14096 KB Output is correct
4 Correct 153 ms 17880 KB Output is correct
5 Correct 174 ms 22276 KB Output is correct
6 Correct 240 ms 20096 KB Output is correct
7 Correct 76 ms 15316 KB Output is correct
8 Correct 156 ms 19812 KB Output is correct
9 Correct 149 ms 21576 KB Output is correct
10 Correct 124 ms 21464 KB Output is correct
11 Correct 15 ms 10452 KB Output is correct
12 Correct 99 ms 14100 KB Output is correct
13 Correct 89 ms 17536 KB Output is correct
14 Correct 209 ms 22204 KB Output is correct
15 Correct 127 ms 17796 KB Output is correct
16 Correct 129 ms 17796 KB Output is correct
17 Correct 144 ms 17760 KB Output is correct
18 Correct 112 ms 17784 KB Output is correct
19 Correct 139 ms 17776 KB Output is correct
20 Correct 73 ms 15352 KB Output is correct
21 Correct 31 ms 11360 KB Output is correct
22 Correct 95 ms 15896 KB Output is correct
23 Correct 107 ms 16112 KB Output is correct
24 Correct 100 ms 17648 KB Output is correct
25 Correct 96 ms 16172 KB Output is correct
26 Correct 127 ms 20244 KB Output is correct
27 Correct 254 ms 21868 KB Output is correct
28 Correct 158 ms 17464 KB Output is correct
29 Correct 173 ms 20192 KB Output is correct
30 Correct 71 ms 15312 KB Output is correct
31 Correct 153 ms 21576 KB Output is correct
32 Correct 161 ms 19612 KB Output is correct
33 Correct 117 ms 20676 KB Output is correct
34 Correct 158 ms 19908 KB Output is correct
35 Correct 117 ms 18736 KB Output is correct
36 Correct 112 ms 18360 KB Output is correct
37 Correct 91 ms 17864 KB Output is correct
38 Correct 109 ms 19840 KB Output is correct
39 Correct 112 ms 21564 KB Output is correct
40 Correct 121 ms 19700 KB Output is correct
41 Correct 114 ms 18396 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9684 KB Output is correct
2 Correct 7 ms 9656 KB Output is correct
3 Incorrect 7 ms 9600 KB Output isn't correct
4 Halted 0 ms 0 KB -