oj.uz

Submission #1048840

# Submission time Handle Problem Language Result Execution time Memory
1048840 2024-08-08T09:46:25 Z mychecksedad Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 1037524 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){
				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(p == u) break;
					if(h[p] >= w){
						node[{p, w}] = co++;
						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());
		for(int p: F[i]){
			// cout << i << ' ' <<p << '\n';
			node[{i, p}] = co++;
		}
		for(int j = 0; j + 1 < F[i].size(); ++j){
			// cout << F[i][j] << ' ';
			g[node[{i, F[i][j]}]].pb({node[{i, F[i][j + 1]}], F[i][j + 1] - F[i][j]});
			g[node[{i, F[i][j + 1]}]].pb({node[{i, F[i][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;
				for(int j = i; j <= u; ++j){
					if(h[j] >= w){
						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:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |       int mid = l+r>>1;
      |                 ~^~
walk.cpp:78:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int j = 0; j + 1 < F[i].size(); ++j){
      |                  ~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 142428 KB Output is correct
2 Correct 18 ms 142428 KB Output is correct
3 Correct 18 ms 142336 KB Output is correct
4 Correct 18 ms 142428 KB Output is correct
5 Correct 19 ms 142612 KB Output is correct
6 Correct 20 ms 142524 KB Output is correct
7 Correct 19 ms 142428 KB Output is correct
8 Correct 20 ms 142428 KB Output is correct
9 Correct 19 ms 142332 KB Output is correct
10 Correct 19 ms 142428 KB Output is correct
11 Correct 19 ms 142300 KB Output is correct
12 Correct 19 ms 142328 KB Output is correct
13 Correct 19 ms 142428 KB Output is correct
14 Correct 19 ms 142392 KB Output is correct
15 Correct 19 ms 142392 KB Output is correct
16 Correct 19 ms 142428 KB Output is correct
17 Correct 21 ms 142456 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 142424 KB Output is correct
2 Correct 19 ms 142308 KB Output is correct
3 Correct 899 ms 272720 KB Output is correct
4 Correct 891 ms 310104 KB Output is correct
5 Correct 693 ms 287756 KB Output is correct
6 Correct 871 ms 273912 KB Output is correct
7 Correct 681 ms 287824 KB Output is correct
8 Correct 1195 ms 308920 KB Output is correct
9 Correct 711 ms 282984 KB Output is correct
10 Correct 1305 ms 356400 KB Output is correct
11 Correct 463 ms 227428 KB Output is correct
12 Correct 361 ms 222976 KB Output is correct
13 Correct 1101 ms 333136 KB Output is correct
14 Correct 1698 ms 213916 KB Output is correct
15 Correct 943 ms 208220 KB Output is correct
16 Correct 310 ms 208720 KB Output is correct
17 Correct 291 ms 206932 KB Output is correct
18 Execution timed out 4038 ms 213616 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 161580 KB Output is correct
2 Runtime error 2190 ms 1037524 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 93 ms 161580 KB Output is correct
2 Runtime error 2190 ms 1037524 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 19 ms 142428 KB Output is correct
2 Correct 18 ms 142428 KB Output is correct
3 Correct 18 ms 142336 KB Output is correct
4 Correct 18 ms 142428 KB Output is correct
5 Correct 19 ms 142612 KB Output is correct
6 Correct 20 ms 142524 KB Output is correct
7 Correct 19 ms 142428 KB Output is correct
8 Correct 20 ms 142428 KB Output is correct
9 Correct 19 ms 142332 KB Output is correct
10 Correct 19 ms 142428 KB Output is correct
11 Correct 19 ms 142300 KB Output is correct
12 Correct 19 ms 142328 KB Output is correct
13 Correct 19 ms 142428 KB Output is correct
14 Correct 19 ms 142392 KB Output is correct
15 Correct 19 ms 142392 KB Output is correct
16 Correct 19 ms 142428 KB Output is correct
17 Correct 21 ms 142456 KB Output is correct
18 Correct 19 ms 142424 KB Output is correct
19 Correct 19 ms 142308 KB Output is correct
20 Correct 899 ms 272720 KB Output is correct
21 Correct 891 ms 310104 KB Output is correct
22 Correct 693 ms 287756 KB Output is correct
23 Correct 871 ms 273912 KB Output is correct
24 Correct 681 ms 287824 KB Output is correct
25 Correct 1195 ms 308920 KB Output is correct
26 Correct 711 ms 282984 KB Output is correct
27 Correct 1305 ms 356400 KB Output is correct
28 Correct 463 ms 227428 KB Output is correct
29 Correct 361 ms 222976 KB Output is correct
30 Correct 1101 ms 333136 KB Output is correct
31 Correct 1698 ms 213916 KB Output is correct
32 Correct 943 ms 208220 KB Output is correct
33 Correct 310 ms 208720 KB Output is correct
34 Correct 291 ms 206932 KB Output is correct
35 Execution timed out 4038 ms 213616 KB Time limit exceeded
36 Halted 0 ms 0 KB -