oj.uz

Submission #1051153

# Submission time Handle Problem Language Result Execution time Memory
1051153 2024-08-09T21:16:25 Z Lalic Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 776228 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

ll st[20][100005];
int lg[100005];

void calc(int n){
	lg[0]=lg[1]=0;
	for(int i=2;i<=100000;i++) lg[i]=lg[(i>>1)]+1;
	
	for(int i=1;i<=18;i++)
		for(int j=0;j<n;j++)
			st[i][j]=max(st[i-1][j], st[i-1][min(j+(1<<(i-1)), n)]);
}

ll getMax(int l, int r){
	int pot=lg[r-l+1];
	return max(st[pot][l], st[pot][r-(1<<pot)+1]);
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n=(int)x.size(), m=(int)l.size();
	
	for(int i=0;i<n;i++) st[0][i]=h[i];
	calc(n);
	
	map<pii, ll> dist;
	dist[{s, 0}]=0;
	
	vector<vector<int>> proc(n);
	proc[s].pb(0); proc[g].pb(0);
	
	map<pii, vector<pii>> adj;
	for(int i=0;i<m;i++){
		int curr=l[i];
		while(curr!=r[i]){
			int low=curr+1, high=r[i]-1, best=r[i];
			
			while(low<=high){
				int mid=(low+high)>>1;
				if(getMax(curr+1, mid)>=y[i]){
					best=mid;
					high=mid-1;
				}
				else low=mid+1;
			}
			
			proc[curr].pb(y[i]);
			proc[best].pb(y[i]);
			
			//~ cout << "added: " << curr << " -> " << best << " at " << y[i] << "\n";
			adj[{curr, y[i]}].pb({best, y[i]});
			adj[{best, y[i]}].pb({curr, y[i]});
			curr=best;
		}
	}
	
	for(int i=0;i<n;i++) sort(all(proc[i]));
	
	for(int i=0;i<n;i++){
		for(int j=1;j<(int)proc[i].size();j++)
			adj[{i, proc[i][j-1]}].pb({i, proc[i][j]}), adj[{i, proc[i][j]}].pb({i, proc[i][j-1]});
	}
	
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<>> pq;
	pq.push({0ll, {s, 0}});
	while(!pq.empty()){
		ll d=pq.top().fi;
		int id=pq.top().se.fi, alt=pq.top().se.se;
		pq.pop();
		
		if(dist[{id, alt}]<d) continue;
		
		for(auto u : adj[{id, alt}]){
			if(dist.find(u)==dist.end() || dist[u]>d+(ll)(abs(u.se-alt)+abs(x[u.fi]-x[id]))){
				dist[u]=d+(ll)(abs(u.se-alt)+abs(x[u.fi]-x[id]));
				pq.push({dist[u], u});
			}
		}
	}
	
	if(dist.find({g, 0})==dist.end()) return -1;
	return dist[{g, 0}];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 1 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 15032 KB Output is correct
9 Correct 1 ms 14940 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 1 ms 14940 KB Output is correct
13 Correct 1 ms 14940 KB Output is correct
14 Correct 1 ms 14940 KB Output is correct
15 Correct 1 ms 14940 KB Output is correct
16 Correct 1 ms 14940 KB Output is correct
17 Correct 2 ms 14940 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 1 ms 14940 KB Output is correct
3 Correct 1951 ms 190356 KB Output is correct
4 Correct 1362 ms 192844 KB Output is correct
5 Correct 531 ms 131920 KB Output is correct
6 Correct 470 ms 116664 KB Output is correct
7 Correct 529 ms 131988 KB Output is correct
8 Correct 2664 ms 242088 KB Output is correct
9 Correct 683 ms 136272 KB Output is correct
10 Correct 2146 ms 270652 KB Output is correct
11 Correct 640 ms 101204 KB Output is correct
12 Correct 229 ms 63548 KB Output is correct
13 Correct 1737 ms 236368 KB Output is correct
14 Correct 140 ms 50516 KB Output is correct
15 Correct 278 ms 62808 KB Output is correct
16 Correct 290 ms 66132 KB Output is correct
17 Correct 252 ms 64336 KB Output is correct
18 Correct 356 ms 70456 KB Output is correct
19 Correct 9 ms 16988 KB Output is correct
20 Correct 96 ms 38056 KB Output is correct
21 Correct 259 ms 62396 KB Output is correct
22 Correct 324 ms 62508 KB Output is correct
23 Correct 400 ms 77248 KB Output is correct
24 Correct 266 ms 64160 KB Output is correct
25 Correct 223 ms 63824 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 31828 KB Output is correct
2 Execution timed out 4065 ms 776228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 31828 KB Output is correct
2 Execution timed out 4065 ms 776228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 1 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 15032 KB Output is correct
9 Correct 1 ms 14940 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 1 ms 14940 KB Output is correct
13 Correct 1 ms 14940 KB Output is correct
14 Correct 1 ms 14940 KB Output is correct
15 Correct 1 ms 14940 KB Output is correct
16 Correct 1 ms 14940 KB Output is correct
17 Correct 2 ms 14940 KB Output is correct
18 Correct 2 ms 14940 KB Output is correct
19 Correct 1 ms 14940 KB Output is correct
20 Correct 1951 ms 190356 KB Output is correct
21 Correct 1362 ms 192844 KB Output is correct
22 Correct 531 ms 131920 KB Output is correct
23 Correct 470 ms 116664 KB Output is correct
24 Correct 529 ms 131988 KB Output is correct
25 Correct 2664 ms 242088 KB Output is correct
26 Correct 683 ms 136272 KB Output is correct
27 Correct 2146 ms 270652 KB Output is correct
28 Correct 640 ms 101204 KB Output is correct
29 Correct 229 ms 63548 KB Output is correct
30 Correct 1737 ms 236368 KB Output is correct
31 Correct 140 ms 50516 KB Output is correct
32 Correct 278 ms 62808 KB Output is correct
33 Correct 290 ms 66132 KB Output is correct
34 Correct 252 ms 64336 KB Output is correct
35 Correct 356 ms 70456 KB Output is correct
36 Correct 9 ms 16988 KB Output is correct
37 Correct 96 ms 38056 KB Output is correct
38 Correct 259 ms 62396 KB Output is correct
39 Correct 324 ms 62508 KB Output is correct
40 Correct 400 ms 77248 KB Output is correct
41 Correct 266 ms 64160 KB Output is correct
42 Correct 223 ms 63824 KB Output is correct
43 Correct 106 ms 31828 KB Output is correct
44 Execution timed out 4065 ms 776228 KB Time limit exceeded
45 Halted 0 ms 0 KB -