oj.uz

Submission #1048854

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 142428 KB Output is correct
2 Correct 19 ms 142312 KB Output is correct
3 Incorrect 19 ms 142424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 142428 KB Output is correct
2 Correct 19 ms 142428 KB Output is correct
3 Correct 678 ms 281976 KB Output is correct
4 Correct 677 ms 296784 KB Output is correct
5 Correct 439 ms 278304 KB Output is correct
6 Correct 421 ms 262480 KB Output is correct
7 Correct 457 ms 278388 KB Output is correct
8 Correct 844 ms 321444 KB Output is correct
9 Correct 469 ms 273056 KB Output is correct
10 Correct 904 ms 356660 KB Output is correct
11 Correct 321 ms 216916 KB Output is correct
12 Correct 184 ms 200272 KB Output is correct
13 Correct 808 ms 326816 KB Output is correct
14 Correct 207 ms 198996 KB Output is correct
15 Incorrect 208 ms 200788 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 161824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 161824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 142428 KB Output is correct
2 Correct 19 ms 142312 KB Output is correct
3 Incorrect 19 ms 142424 KB Output isn't correct
4 Halted 0 ms 0 KB -