oj.uz

Submission #455198

# Submission time Handle Problem Language Result Execution time Memory
455198 2021-08-05T16:45:22 Z blue Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 106028 KB 
#include "walk.h"
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int N;
vector<int> X;
vector<int> H;

int M;
vector<int> L;
vector<int> R;
vector<int> Y;

int S;
int G;

const int INF = 1e9 + 1;
const int MX = 100'000;
const long long LONG_INF = 1'000'000'000'000'000'0LL;


int higher_skywalk(int w1, int w2)
{
	if(w1 == -1) return w2;
	else if(w2 == -1) return w1;
	else if(Y[w1] == Y[w2]) return max(w1, w2);
	else if(Y[w1] > Y[w2]) return w1;
	else return w2;
}

bool skywalk_leq(int w1, int w2)
{
	if(w1 == -1) return 1;
	if(w2 == -1)
	{
		return 0;
	}
	if(Y[w1] == Y[w2]) return w1 <= w2;
	return Y[w1] < Y[w2];
}

bool skywalk_less(int w1, int w2)
{
	if(w1 == -1 && w2 == -1) return 0;
	else if(w1 == -1 && w2 != -1) return 1;
	else if(w1 != -1 && w2 == -1) return 0;
	else
	{
		if(w1 == w2) return 0;
		if(Y[w1] == Y[w2]) return w1 < w2;
		return Y[w1] < Y[w2];
	}
}

struct point
{
	int b; //building
	int s; //skywalk
	int i;

	point()
	{
		;
	}

	point(int B, int S)
	{
		b = B;
		s = S;
	}

	point(int B, int S, int I)
	{
		b = B;
		s = S;
		i = I;
	}
};

bool operator < (point A, point B)
{
	if(A.b == B.b) return A.s < B.s;
	return A.b < B.b;
}

set<point> points;

struct walk_segtree
{
	int l;
	int r;
	vector<int> w;

	walk_segtree* left = NULL;
	walk_segtree* right = NULL;

	walk_segtree()
	{
		;
	}

	walk_segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r) return;
		int m = (l+r)/2;
		left = new walk_segtree(l, m);
		right = new walk_segtree(m+1, r);
	}

	void add_skywalk(int W)
	{
		if(R[W] < l || r < L[W]) return;
		else if(L[W] <= l && r <= R[W])
		{
			w.push_back(W);
		}
		else
		{
			left->add_skywalk(W);
			right->add_skywalk(W);
		}
	}

	void sort_skywalks()
	{
		sort(w.begin(), w.end(), [] (int u, int v)
		{
			return Y[u] < Y[v];
		});

		if(left != NULL)
		{
			left->sort_skywalks();
			right->sort_skywalks();
		}
	}

	int locate_lower(int I, int W)
	{
		if(r < I || I < l) return -1;

		int ind = -1;
		for(int bit = 20; bit >= 0; bit--)
		{
			if(ind + (1 << bit) >= w.size()) continue;
			if(skywalk_leq(W, w[ind + (1 << bit)])) continue;
			ind += (1 << bit);
		}

		int curr_best = (ind == -1 ? -1 : w[ind]);

		if(left != NULL)
		{
			curr_best = higher_skywalk(curr_best, left->locate_lower(I, W));
			curr_best = higher_skywalk(curr_best, right->locate_lower(I, W));
		}

		return curr_best;
	}
};

int taller_building(int b1, int b2)
{
	if(b1 == -1) return b2;
	else if(b2 == -1) return b1;
	else if(H[b1] > H[b2]) return b1;
	else return b2;
}

struct build_segtree
{
	int l;
	int r;
	int h; //maximum height of a building

	build_segtree* left = NULL;
	build_segtree* right = NULL;

	build_segtree()
	{
		;
	}

	build_segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r) h = H[L];
		else
		{
			int m = (l+r)/2;
			left = new build_segtree(l, m);
			right = new build_segtree(m+1, r);
			h = max(left->h, right->h);
		}
	}

	int rangemax(int L, int R)
	{
		if(R < L) return -INF;
		else if(R < l || r < L) return -INF;
		else if(L <= l && r <= R) return h;
		else return max(left->rangemax(L, R), right->rangemax(L, R));
	}
};






vector<int>* edge;
vector<long long>* dist;
vector<long long> src_dist(1'000'000, LONG_INF);

void add_edge(int u, int v, long long w)
{
	edge[u].push_back(v);
	dist[u].push_back(w);

	edge[v].push_back(u);
	dist[v].push_back(w);
	// cerr << u << ' ' << v << ' ' << w << '\n';

	assert(w >= 0);
}

struct pos
{
	int i;
};

bool operator < (pos A, pos B)
{
	if(src_dist[A.i] == src_dist[B.i]) return A.i < B.i;
	return src_dist[A.i] < src_dist[B.i];
}





long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
	// cerr << "A\n";
	N = x.size();
	X = x;
	H = h;

	M = l.size();
	L = l;
	R = r;
	Y = y;

	S = s;
	G = g;

	walk_segtree S_W(0, N-1);
	for(int j = 0; j < M; j++)
		S_W.add_skywalk(j);

	S_W.sort_skywalks();

	// cerr << "B\n";


	for(int j = 0; j < M; j++)
	{
		int LL = S_W.locate_lower(L[j], j);
		if(LL != -1)
			points.insert(point(L[j], LL));

		int RL = S_W.locate_lower(R[j], j);
		if(RL != -1)
			points.insert(point(R[j], RL));
	}

	// cerr << "C\n";



	for(int j = 0; j < M; j++)
	{
		if(L[j] <= S && S <= R[j] && Y[j] <= H[S])
		{
			points.insert(point(S, j));
		}

		if(L[j] <= G && G <= R[j] && Y[j] <= H[G])
			points.insert(point(G, j));
	}

	// cerr << "D\n";




	build_segtree S_B(0, N-1);

	// cerr << "E\n";



	int S_skywalk = M;
	L.push_back(S);
	R.push_back(S);
	Y.push_back(0);

	int G_skywalk = M+1;
	L.push_back(G);
	R.push_back(G);
	Y.push_back(0);

	// cerr << "F\n";





	for(int j = 0; j < M; j++)
	{
		// cerr << "j = " << j << '\n';
		for(int PT: vector<int>{S, G})
		{
			// S_B.rangemax(L[j], min(R[j], PT));
			// cerr << "query done\n";
			if(L[j] <= PT && S_B.rangemax(L[j], min(R[j], PT)) >= Y[j])
			{
				// cerr << "entered if statement\n";
				int lo = L[j];
				int hi = min(R[j], PT);
				int mid;
				// cerr << "check\n";
				while(lo != hi)
				{
					mid = (lo+hi)/2 + 1;
					// cerr << lo << ' ' << hi << ' ' << mid << '\n';
					if(S_B.rangemax(mid, hi) >= Y[j])
						lo = mid;
					else
						hi = mid-1;
				}
				// cerr << lo << ' ' << hi << '\n';
				mid = lo;

				if(H[mid] >= Y[j])
				{
					int tmp = S_W.locate_lower(mid, j);
					if(tmp != -1)
					{
						points.insert(point(mid, j));
						points.insert(point(mid, tmp));
					}
				}
			}
			// else cerr << "not entered\n";

			// cerr << "left done\n";



			if(PT <= R[j] && S_B.rangemax(max(L[j], PT), R[j]) >= Y[j])
			{
				int lo = max(L[j], PT);
				int hi = R[j];
				int mid;
				while(lo != hi)
				{
					mid = (lo+hi)/2;
					if(S_B.rangemax(lo, mid) >= Y[j])
						hi = mid;
					else
						lo = mid+1;
				}
				mid = lo;

				if(H[mid] >= Y[j])
				{
					int tmp = S_W.locate_lower(mid, j);
					if(tmp != -1)
					{
						points.insert(point(mid, j));
						points.insert(point(mid, tmp));
					}
				}
			}
		}
	}


	// cerr << "G\n";


	int P = points.size();
	vector<point> points_vector;
	int ct = 0;
	while(!points.empty())
	{
		point pt = *points.begin();
		points.erase(points.begin());
		ct++;
		pt.i = ct-1;
		points_vector.push_back(pt);
	}

	// cerr << "H\n";

	ct++;
	points_vector.push_back(point(S, S_skywalk, ct-1));
	int S_vertex = ct-1;

	ct++;
	points_vector.push_back(point(G, G_skywalk, ct-1));
	int G_vertex = ct-1;




	// for(point pt: points_vector) cerr << X[pt.b] << ' ' << Y[pt.s] << '\n';

	// cerr << "check\n";

	// cerr << "I\n";


	edge = new vector<int>[ct];
	dist = new vector<long long>[ct];

	sort(points_vector.begin(), points_vector.end(), [] (point p1, point p2)
	{
		if(p1.b == p2.b) return (skywalk_less(p1.s, p2.s));
		return p1.b < p2.b;
	});

	for(int z = 0; z+1 < points_vector.size(); z++)
	{
		point p1 = points_vector[z];
		point p2 = points_vector[z+1];
		if(p1.b == p2.b)
		{
			add_edge(p1.i, p2.i, Y[p2.s] - Y[p1.s]);
			// cerr << p1.b << ' ' << p1.s << "    " << p2.b << ' ' << p2.s << '\n';
			// cerr << "adding edge from " << X[p1.b] << ' ' << Y[p1.s] << " to " << X[p2.b] << ' ' << Y[p2.s] << " with weight " << Y[p2.s] - Y[p1.s] << '\n';
		}
	}






	sort(points_vector.begin(), points_vector.end(), [] (point p1, point p2)
	{
		if(p1.s == p2.s) return p1.b < p2.b;
		return skywalk_less(p1.s, p2.s);
	});

	for(int z = 0; z+1 < points_vector.size(); z++)
	{
		point p1 = points_vector[z];
		point p2 = points_vector[z+1];
		if(p1.s == p2.s)
		{
			add_edge(p1.i, p2.i, X[p2.b] - X[p1.b]);
			// cerr << "adding edge from " << X[p1.b] << ' ' << Y[p1.s] << " to " << X[p2.b] << ' ' << Y[p2.s] << " with weight " << X[p2.b] - X[p1.b] << '\n';
		}
	}

	// cerr << "Q\n";

	// if(N+M > 200)
	// {
	// 	while(1);
	// }


	src_dist[S_vertex] = 0;
	set<pos> tbv;
	for(int i = 0; i < ct; i++) tbv.insert(pos{i});
	while(!tbv.empty())
	{
		int u = tbv.begin()->i;
		tbv.erase(tbv.begin());
		// cerr << "u = " << u << '\n';
		// cerr << src_dist[u] << '\n';

		for(int e = 0; e < edge[u].size(); e++)
		{
			int v = edge[u][e];
			long long w = dist[u][e];

			if(src_dist[v] > src_dist[u] + w)
			{
				tbv.erase(pos{v});
				src_dist[v] = src_dist[u] + w;
				// cerr << "w = " << w << '\n';
				tbv.insert(pos{v});
			}
		}
	}
	// cerr << "Z\n";

	long long ans = src_dist[G_vertex];
	if(ans >= LONG_INF)
		ans = -1;




	return ans;
}

Compilation message

walk.cpp: In member function 'int walk_segtree::locate_lower(int, int)':
walk.cpp:151:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |    if(ind + (1 << bit) >= w.size()) continue;
      |       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
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:441:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  441 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:464:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  464 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:493:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  493 |   for(int e = 0; e < edge[u].size(); e++)
      |                  ~~^~~~~~~~~~~~~~~~
walk.cpp:400:6: warning: unused variable 'P' [-Wunused-variable]
  400 |  int P = points.size();
      |      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8164 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 5 ms 8140 KB Output is correct
6 Correct 6 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 5 ms 8128 KB Output is correct
9 Correct 5 ms 8096 KB Output is correct
10 Correct 6 ms 8140 KB Output is correct
11 Correct 6 ms 8136 KB Output is correct
12 Correct 5 ms 8140 KB Output is correct
13 Correct 5 ms 8132 KB Output is correct
14 Correct 6 ms 8140 KB Output is correct
15 Correct 4 ms 8132 KB Output is correct
16 Correct 6 ms 8140 KB Output is correct
17 Correct 6 ms 8140 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 1902 ms 71788 KB Output is correct
4 Correct 1938 ms 100976 KB Output is correct
5 Incorrect 1274 ms 74964 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 34320 KB Output is correct
2 Correct 3128 ms 100524 KB Output is correct
3 Correct 3693 ms 106028 KB Output is correct
4 Execution timed out 4046 ms 98164 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 34320 KB Output is correct
2 Correct 3128 ms 100524 KB Output is correct
3 Correct 3693 ms 106028 KB Output is correct
4 Execution timed out 4046 ms 98164 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8164 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 5 ms 8140 KB Output is correct
6 Correct 6 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 5 ms 8128 KB Output is correct
9 Correct 5 ms 8096 KB Output is correct
10 Correct 6 ms 8140 KB Output is correct
11 Correct 6 ms 8136 KB Output is correct
12 Correct 5 ms 8140 KB Output is correct
13 Correct 5 ms 8132 KB Output is correct
14 Correct 6 ms 8140 KB Output is correct
15 Correct 4 ms 8132 KB Output is correct
16 Correct 6 ms 8140 KB Output is correct
17 Correct 6 ms 8140 KB Output is correct
18 Correct 5 ms 8140 KB Output is correct
19 Correct 5 ms 8140 KB Output is correct
20 Correct 1902 ms 71788 KB Output is correct
21 Correct 1938 ms 100976 KB Output is correct
22 Incorrect 1274 ms 74964 KB Output isn't correct
23 Halted 0 ms 0 KB -