oj.uz

Submission #455191

# Submission time Handle Problem Language Result Execution time Memory
455191 2021-08-05T16:40:46 Z blue Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 25696 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(100+MX, 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));
					}
				}
			}
		}
	}
	

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

	// 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";


	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:443:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  443 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:466:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  466 |  for(int z = 0; z+1 < points_vector.size(); z++)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
walk.cpp:490:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  490 |   for(int e = 0; e < edge[u].size(); e++)
      |                  ~~^~~~~~~~~~~~~~~~
walk.cpp:405:6: warning: unused variable 'P' [-Wunused-variable]
  405 |  int P = points.size();
      |      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Execution timed out 4038 ms 25696 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 12680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 12680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 2 ms 1052 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 1 ms 972 KB Output is correct
20 Execution timed out 4038 ms 25696 KB Time limit exceeded
21 Halted 0 ms 0 KB -