oj.uz

Submission #951352

# Submission time Handle Problem Language Result Execution time Memory
951352 2024-03-21T16:46:15 Z qin Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 669796 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
ll min_distance(vv<int> x, vv<int> h, vv<int> l, vv<int> r, vv<int> y, int s, int e){
		int n = ssize(x), m = ssize(y); 
		vv<set<int>> beg(n), ed(n);
		for(int i = 0; i < m; ++i) beg[l[i]].emplace(y[i]), ed[r[i]].emplace(y[i]);
		for(int i = 0; i < n; ++i){
				vv<int> to_remove;
				for(int u : beg[i]){
						auto it = lower_bound(all(ed[i]), u);
						if(it != ed[i].end() && *it == u) to_remove.emplace_back(u);
				}
				for(int u : to_remove) beg[i].erase(u), ed[i].erase(u);
		}
		
		set<int> active;
		vv<vv<pii>> g(1);
		int cnt = 0;
		map<pii, int> mp;
		int a = -1, b = -1;
		for(int i = 0; i < n; ++i){
				vv<pii> nr;
				if(i == s || i == e){
						nr.emplace_back(++cnt, 0), g.emplace_back(vv<pii>());
						if(a == -1) a = cnt;
						else b = cnt;
						mp[pii(i, 0)] = cnt;
				}
				
				for(int u : beg[i]) active.emplace(u);
				for(int u : active){
						if(u > h[i]) break;
						mp[pii(i, u)] = ++cnt, nr.emplace_back(cnt, u), g.emplace_back(vv<pii>());
				}
				for(int u : ed[i]) active.erase(u);
				//~ printf("%d:\n", i);
				for(int j = 0; j < ssize(nr)-1; ++j) g[nr[j].fi].emplace_back(nr[j+1].fi, abs(nr[j].se-nr[j+1].se)), g[nr[j+1].fi].emplace_back(nr[j].fi, abs(nr[j].se-nr[j+1].se));
				//~ pn;
		}
		map<int, int> last;
		for(int i = 0; i < n; ++i){
				//~ printf("%d:\n", i);
				for(int u : active){
						if(u > h[i]) break;
						//~ printf("%d %d, ", u, abs(x[last[u]]-x[i]));
						g[mp[pii(i, u)]].emplace_back(mp[pii(last[u], u)], abs(x[last[u]]-x[i])), g[mp[pii(last[u], u)]].emplace_back(mp[pii(i, u)], abs(x[last[u]]-x[i]));
						last[u] = i;
				}
				//~ pn;
				for(int u : beg[i]) active.emplace(u), last[u] = i;
				for(int u : ed[i]) active.erase(u), last[u] = 0;
		}
		n = ssize(g)-1;
		vv<ll> dist(n+1, infll);
		dist[a] = 0; priority_queue<pli> pq; pq.emplace(0, a);
		while(ssize(pq)){
				int X = pq.top().se; ll d = -pq.top().fi; pq.pop();
				if(dist[X] != d) continue;
				for(pii u : g[X])
						if(d+u.se < dist[u.fi])
								dist[u.fi] = d+u.se, pq.emplace(-dist[u.fi], u.fi);
		}
		if(dist[b] == infll) return -1;
		else return dist[b];
		return 0;
}
#ifdef LOCAL
signed main(){
		int T = 1;
		for(++T; --T; ){
				int n, m, s, g; scanf("%d%d", &n, &m);
				vv<int> x(n), h(n), l(m), r(m), y(m);
				for(int i = 0; i < n; ++i) scanf("%d", &x[i]);
				for(int i = 0; i < n; ++i) scanf("%d", &h[i]);
				for(int i = 0; i < m; ++i) scanf("%d", &l[i]);
				for(int i = 0; i < m; ++i) scanf("%d", &r[i]);
				for(int i = 0; i < m; ++i) scanf("%d", &y[i]);
				scanf("%d%d", &s, &g);
				ll result = min_distance(x, h, l, r, y, s, g);
				printf("%lld\n", result);
		}
		return 0;
}
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1126 ms 119444 KB Output is correct
4 Correct 1074 ms 135132 KB Output is correct
5 Correct 766 ms 117792 KB Output is correct
6 Correct 745 ms 105216 KB Output is correct
7 Correct 771 ms 118780 KB Output is correct
8 Correct 1415 ms 148492 KB Output is correct
9 Correct 837 ms 118672 KB Output is correct
10 Correct 1408 ms 178020 KB Output is correct
11 Correct 552 ms 74740 KB Output is correct
12 Correct 317 ms 57652 KB Output is correct
13 Correct 1303 ms 159848 KB Output is correct
14 Correct 352 ms 55248 KB Output is correct
15 Correct 324 ms 55288 KB Output is correct
16 Correct 272 ms 54284 KB Output is correct
17 Correct 260 ms 51196 KB Output is correct
18 Correct 389 ms 66780 KB Output is correct
19 Correct 9 ms 3220 KB Output is correct
20 Correct 117 ms 29568 KB Output is correct
21 Correct 225 ms 50364 KB Output is correct
22 Correct 236 ms 51700 KB Output is correct
23 Correct 392 ms 65808 KB Output is correct
24 Correct 239 ms 52272 KB Output is correct
25 Correct 226 ms 51180 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12540 KB Output is correct
2 Execution timed out 4086 ms 669796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12540 KB Output is correct
2 Execution timed out 4086 ms 669796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1126 ms 119444 KB Output is correct
21 Correct 1074 ms 135132 KB Output is correct
22 Correct 766 ms 117792 KB Output is correct
23 Correct 745 ms 105216 KB Output is correct
24 Correct 771 ms 118780 KB Output is correct
25 Correct 1415 ms 148492 KB Output is correct
26 Correct 837 ms 118672 KB Output is correct
27 Correct 1408 ms 178020 KB Output is correct
28 Correct 552 ms 74740 KB Output is correct
29 Correct 317 ms 57652 KB Output is correct
30 Correct 1303 ms 159848 KB Output is correct
31 Correct 352 ms 55248 KB Output is correct
32 Correct 324 ms 55288 KB Output is correct
33 Correct 272 ms 54284 KB Output is correct
34 Correct 260 ms 51196 KB Output is correct
35 Correct 389 ms 66780 KB Output is correct
36 Correct 9 ms 3220 KB Output is correct
37 Correct 117 ms 29568 KB Output is correct
38 Correct 225 ms 50364 KB Output is correct
39 Correct 236 ms 51700 KB Output is correct
40 Correct 392 ms 65808 KB Output is correct
41 Correct 239 ms 52272 KB Output is correct
42 Correct 226 ms 51180 KB Output is correct
43 Correct 66 ms 12540 KB Output is correct
44 Execution timed out 4086 ms 669796 KB Time limit exceeded
45 Halted 0 ms 0 KB -