oj.uz

Submission #1048858

# Submission time Handle Problem Language Result Execution time Memory
1048858 2024-08-08T09:56:17 Z mychecksedad Sky Walking (IOI19_walk) C++17
24 / 100
 2057 ms 806992 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 2e6+100, K = 20, M=2E5;

int n, m;
map<pair<int, int>, int> node;
vector<pair<int,int>> G[N];
vector<int> F[N];
vector<pair<int, ll>> g[N];
int rmq[M][K];
int get(int l, int r){
	int k = log2(r-l+1);
	return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
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 gg) {
	n = x.size();
	m = l.size();
	for(int i = 0; i < m; ++i){
		int u = l[i], v = r[i], L = y[i];
		F[u].pb(L);
		F[v].pb(L);
		G[u].pb({v, L});
		G[v].pb({u, L});
	}

	for(int i = 1; i <= n; ++i) rmq[i][0] = h[i - 1];
	for(int j = 1; j < K ;++j){
		for(int i = 1; i + (1<<j) <= n+1; ++i){
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j-1]);
		}
	}

	int co = 0;
	for(int i = 0; i < n; ++i){
		for(auto U: G[i]){
			int u = U.ff; ll w = U.ss;
			if(u > i){
				if(node[{i,w}] == 0)
				node[{i, w}] = co++;
				int last = i;
				while(last < u){
					int l = last + 2, r = n, p = n + 1;
					while(l <= r){
						int mid = l+r>>1;
						if(get(last + 2, mid) >= w){
							p = mid;
							r = mid - 1;
						}else{
							l = mid + 1;
						}
					}
					--p;
					if(h[p] >= w){
						if(node[{p,w}]==0)
						node[{p, w}] = co++;
						// cout << x[p] << ' ' << x[last] << '\n';
						g[node[{last, w}]].pb({node[{p,w}], abs(x[p] - x[last])});
						g[node[{p,w}]].pb({node[{last, w}], abs(x[p] - x[last])});
						F[p].pb(w);
					}
					last = p;
				}
				
			}
		}
	}
	for(int i = 0; i < n; ++i){
		F[i].pb(0);
		// F[i].pb(h[i]);
		sort(all(F[i]));
		F[i].erase(unique(all(F[i])), F[i].end());
		vector<int> X;
		if(node[{i,0}]==0) node[{i, 0}] = co++;
		// if(node[{i,h[i]}]==0) node[{i, 0}] = co++;
		for(int p: F[i]){
			// cout << i << ' ' <<p << '\n';
			// node[{i, p}] = co++;
			X.pb(node[{i, p}]);
		}
		for(int j = 0; j + 1 < F[i].size(); ++j){
			// cout << F[i][j] << ' ';
			g[X[j]].pb({X[j+1], F[i][j + 1] - F[i][j]});
			g[X[j + 1]].pb({X[j], F[i][j + 1] - F[i][j]});
		}
		// cout << '\n';
	}
	// cout << "\n";
	// for(int i = 0; i < n; ++i){
	// 	for(auto U: G[i]){
	// 		int u = U.ff; ll w = U.ss;
	// 		if(u > i){
	// 			int last = i;
	// 			int j = u;
	// 			g[node[{last, w}]].pb({node[{j, w}], abs(x[j]-x[last])});
	// 			g[node[{j, w}]].pb({node[{last, w}], abs(x[j]-x[last])});
	// 			last = j;
	// 		}
	// 	}
	// }
	vector<ll> dist(co, 1e15*1ll);
	vector<bool> vis(co);
	priority_queue<pair<ll, int>> Q;
	Q.push({0, node[{s, 0}]});
	dist[node[{s, 0}]] = 0;
	while(!Q.empty()){
		int v = Q.top().ss; Q.pop();
		if(vis[v]) continue;
		// cout  << v << ' ' << dist[v] << '\n';
		vis[v] = 1;
		for(auto U: g[v]){
			int u = U.ff;
			ll w= U.ss;
			if(dist[u] > dist[v] + w){
				dist[u] = dist[v] + w;;
				Q.push({-dist[u], u});
			}
		}
	}
	ll D = dist[node[{gg, 0}]];
	if(D == 1e15*1ll) return -1;
	// cout << node[{gg,0}] << ' ';
	return D;
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:51:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |       int mid = l+r>>1;
      |                 ~^~
walk.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int j = 0; j + 1 < F[i].size(); ++j){
      |                  ~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 142308 KB Output is correct
2 Correct 20 ms 142320 KB Output is correct
3 Correct 20 ms 142428 KB Output is correct
4 Correct 19 ms 142280 KB Output is correct
5 Correct 20 ms 142428 KB Output is correct
6 Correct 21 ms 142580 KB Output is correct
7 Correct 22 ms 142360 KB Output is correct
8 Correct 25 ms 142492 KB Output is correct
9 Correct 20 ms 142380 KB Output is correct
10 Correct 22 ms 142424 KB Output is correct
11 Correct 20 ms 142428 KB Output is correct
12 Correct 20 ms 142388 KB Output is correct
13 Correct 20 ms 142380 KB Output is correct
14 Correct 23 ms 142448 KB Output is correct
15 Correct 19 ms 142428 KB Output is correct
16 Correct 20 ms 142312 KB Output is correct
17 Correct 20 ms 142632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 142424 KB Output is correct
2 Correct 20 ms 142460 KB Output is correct
3 Correct 899 ms 287412 KB Output is correct
4 Correct 848 ms 297808 KB Output is correct
5 Correct 647 ms 278580 KB Output is correct
6 Correct 557 ms 262976 KB Output is correct
7 Correct 659 ms 278684 KB Output is correct
8 Correct 1177 ms 328116 KB Output is correct
9 Correct 661 ms 273808 KB Output is correct
10 Correct 1216 ms 357456 KB Output is correct
11 Correct 406 ms 218676 KB Output is correct
12 Correct 241 ms 200428 KB Output is correct
13 Correct 980 ms 328784 KB Output is correct
14 Correct 229 ms 199108 KB Output is correct
15 Correct 252 ms 200236 KB Output is correct
16 Correct 240 ms 201512 KB Output is correct
17 Correct 230 ms 200112 KB Output is correct
18 Correct 318 ms 203692 KB Output is correct
19 Correct 28 ms 147028 KB Output is correct
20 Correct 125 ms 172408 KB Output is correct
21 Correct 194 ms 198740 KB Output is correct
22 Correct 257 ms 203484 KB Output is correct
23 Correct 319 ms 214588 KB Output is correct
24 Correct 239 ms 203576 KB Output is correct
25 Correct 208 ms 201920 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 160596 KB Output is correct
2 Runtime error 2057 ms 806992 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 160596 KB Output is correct
2 Runtime error 2057 ms 806992 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 142308 KB Output is correct
2 Correct 20 ms 142320 KB Output is correct
3 Correct 20 ms 142428 KB Output is correct
4 Correct 19 ms 142280 KB Output is correct
5 Correct 20 ms 142428 KB Output is correct
6 Correct 21 ms 142580 KB Output is correct
7 Correct 22 ms 142360 KB Output is correct
8 Correct 25 ms 142492 KB Output is correct
9 Correct 20 ms 142380 KB Output is correct
10 Correct 22 ms 142424 KB Output is correct
11 Correct 20 ms 142428 KB Output is correct
12 Correct 20 ms 142388 KB Output is correct
13 Correct 20 ms 142380 KB Output is correct
14 Correct 23 ms 142448 KB Output is correct
15 Correct 19 ms 142428 KB Output is correct
16 Correct 20 ms 142312 KB Output is correct
17 Correct 20 ms 142632 KB Output is correct
18 Correct 25 ms 142424 KB Output is correct
19 Correct 20 ms 142460 KB Output is correct
20 Correct 899 ms 287412 KB Output is correct
21 Correct 848 ms 297808 KB Output is correct
22 Correct 647 ms 278580 KB Output is correct
23 Correct 557 ms 262976 KB Output is correct
24 Correct 659 ms 278684 KB Output is correct
25 Correct 1177 ms 328116 KB Output is correct
26 Correct 661 ms 273808 KB Output is correct
27 Correct 1216 ms 357456 KB Output is correct
28 Correct 406 ms 218676 KB Output is correct
29 Correct 241 ms 200428 KB Output is correct
30 Correct 980 ms 328784 KB Output is correct
31 Correct 229 ms 199108 KB Output is correct
32 Correct 252 ms 200236 KB Output is correct
33 Correct 240 ms 201512 KB Output is correct
34 Correct 230 ms 200112 KB Output is correct
35 Correct 318 ms 203692 KB Output is correct
36 Correct 28 ms 147028 KB Output is correct
37 Correct 125 ms 172408 KB Output is correct
38 Correct 194 ms 198740 KB Output is correct
39 Correct 257 ms 203484 KB Output is correct
40 Correct 319 ms 214588 KB Output is correct
41 Correct 239 ms 203576 KB Output is correct
42 Correct 208 ms 201920 KB Output is correct
43 Correct 83 ms 160596 KB Output is correct
44 Runtime error 2057 ms 806992 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -