oj.uz

Submission #483497

# Submission time Handle Problem Language Result Execution time Memory
483497 2021-10-30T04:27:44 Z blue Sky Walking (IOI19_walk) C++17
57 / 100
 4000 ms 443200 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;


int ht(int i)
{
	if(i > 0) return H[i-1];
	else return Y[-i-1];
}

bool cmp(int i, int j)
{
	if(ht(i) == ht(j)) return i > j;
	else return ht(i) > ht(j);
}


vector<int> newL, newR, newY;




const int mx = 4'000'000;
const long long INF = 1'000'000'000'000'000'000LL;


vector<int> edge[mx];
vector<long long> wt[mx];

void add_edge(int u, int v, long long w)
{
	// cerr << "add edge " << u << ' ' << v << ' ' << w << '\n';
	edge[u].push_back(v);
	wt[u].push_back(w);

	edge[v].push_back(u);
	wt[v].push_back(w);
}

vector<long long> distS(mx, INF);

struct distcomp
{
	int i;
};

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


set<pair<int, int> > points;  //stored by building index + y coordinate







struct loc
{
	int b;
	int y;

	int ind;
};

bool operator < (loc A, loc B)
{
	if(A.y == B.y) return A.b < B.b;
	else return A.y < B.y;
}



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

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

	S = s;
	G = g;



	vector<int> obj;
	for(int i = 0; i < N; i++) obj.push_back(i+1);
	for(int j = 0; j < M; j++) obj.push_back(-(j+1));
	sort(obj.begin(), obj.end(), cmp);

	vector<int> walk_buildings[M];

	set<int> buildings;
	for(int o: obj)
	{
		if(o > 0)
		{
			buildings.insert(o-1);
		}
		else
		{
			int w = -o-1;
			set<int> endpoints;
			endpoints.insert(L[w]);
			endpoints.insert(R[w]);
			points.insert(make_pair(L[w], Y[w]));
			// cerr << "inserting point A " << L[w] << ' ' << Y[w] << '\n';
			points.insert(make_pair(R[w], Y[w]));
			// cerr << "inserting point B " << R[w] << ' ' << Y[w] << '\n';
			walk_buildings[w].push_back(L[w]);
			walk_buildings[w].push_back(R[w]);

			for(int z: {s, g})
			{
				auto f = buildings.lower_bound(z);
				if(f != buildings.end())
					if(L[w] < *f && *f < R[w])
					{
						points.insert(make_pair(*f, Y[w]));
						// cerr << "inserting point C " << *f << ' ' << Y[w] << '\n';
						walk_buildings[w].push_back(*f);
					}
						// endpoints.insert(*f);

				if(f != buildings.begin())
				{
					f--;
					if(L[w] < *f && *f < R[w])
					{
						points.insert(make_pair(*f, Y[w]));
						// cerr << "inserting point D " << *f << ' ' << Y[w] << '\n';
						walk_buildings[w].push_back(*f);
					}
				}
			}
		}
	}

	vector<int> ep[N];

	for(int j = 0; j < M; j++)
	{
		walk_buildings[j].erase(unique(walk_buildings[j].begin(), walk_buildings[j].end()), walk_buildings[j].end());
		for(int i: walk_buildings[j])
			ep[i].push_back(j);
	}

	points.insert(make_pair(S, 0));
	points.insert(make_pair(G, 0));


	vector<int> left_ep[N], right_ep[N];
	for(int j = 0; j < M; j++)
	{
		left_ep[L[j]].push_back(j);
		right_ep[R[j]].push_back(j);
	}

	set< pair<int, int> > curr_walks;
	for(int i = 0; i < N; i++)
	{
		for(int w: left_ep[i])
		{
			curr_walks.insert(make_pair(Y[w], w));
		}

		for(int w: ep[i])
		{
			auto f = curr_walks.find(make_pair(Y[w], w));
			assert(f != curr_walks.end());
			auto f1 = f;

			if(f != curr_walks.begin())
			{
				f--;
				if(L[f->second] <= i && i <= R[f->second] && Y[f->second] <= H[i])
					points.insert(make_pair(i, f->first));
				// cerr << "inserting point " << *f << ' ' << Y[w] << '\n';
			}

			if(f1 != curr_walks.end())
			{
				f1++;
				if(f1 != curr_walks.end())
					if(L[f1->second] <= i && i <= R[f1->second] && Y[f1->second] <= H[i])
						points.insert(make_pair(i, f1->first));
			}
		}

		for(int w: right_ep[i])
		{
			curr_walks.erase(make_pair(Y[w], w));
		}
	}

		// cerr << "all points: ";
		// for(auto p:points) cerr << p.first << ' ' << p.second << '\n';

	vector<loc> places;

	int ct = -1;
	for(auto p: points)
	{
		ct++;
		places.push_back(loc{p.first, p.second, ct});
	}

	sort(places.begin(), places.end(), [] (loc k, loc l)
	{
		if(k.b == l.b)
			return k.y < l.y;
		else
			return k.b < l.b;
	});

	// cerr << "vertical edges: \n";

	for(int i = 0; i+1 < int(places.size()); i++)
	{
		if(places[i].b == places[i+1].b)
			add_edge(places[i].ind, places[i+1].ind, places[i+1].y - places[i].y);
	}

	sort(places.begin(), places.end(), [] (loc k, loc l)
	{
		if(k.y == l.y)
			return k.b < l.b;
		else
			return k.y < l.y;
	});

	// cerr << "horiz edges: \n";

	// cerr << "\n\n\n\nsorted places: \n";
	// for(auto q: places) cerr << q.b << ' ' << q.y << ' ' << q.ind << '\n';
	// cerr << "\n\n\n";

	for(int j = 0; j < M; j++)
	{
		// cerr << "j = " << j << '\n';
		auto f = lower_bound(places.begin(), places.end(), loc{L[j], Y[j], -1});
		auto g = f;
		g++;

		int ite = 0;

		while(1)
		{
			// cerr << "ite = " << ite << '\n';
			ite++;
			// cerr << int(g == places.end()) << '\n';
			if(g == places.end()) break;
			if(g->b > R[j]) break;
			if(g->y != Y[j]) break;
			// cerr << "gb = " << g->b << ", fb = " << f->b << '\n';
			// cerr << "g = " << g->b << ' ' << g->y << ", " << "f = " << f->b << ' ' << f->y << '\n';
			add_edge(f->ind, g->ind, X[g->b] - X[f->b]);
			f++;
			g++;
			// cerr << "done\n";
		}
	}
	// cerr << "j done\n";

	int S_loc, G_loc;

	for(int i = 0; i <= ct; i++)
	{
		if(places[i].b == S && places[i].y == 0)
			S_loc = places[i].ind;
		else if(places[i].b == G && places[i].y == 0)
			G_loc = places[i].ind;
	}


	// for(int i = 0; i <= ct; i++) cerr << "position " << places[i].b << ' ' << places[i].y << " = index " << places[i].ind << '\n';


	distS[S_loc] = 0;

	set<distcomp> tbv;
	for(int i = 0; i <= ct; i++)
		tbv.insert(distcomp{i});

	// cerr << "hello\n";


	while(!tbv.empty())
	{
		int u = tbv.begin()->i;
		tbv.erase(tbv.begin());

		// cerr << "u = " << u << ", distS = " << distS[u] << '\n';

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

			if(distS[v] <= distS[u] + w) continue;
			tbv.erase(distcomp{v});
			distS[v] = distS[u] + w;
			tbv.insert(distcomp{v});
		}
	}

	if(distS[G_loc] >= INF)
		distS[G_loc] = -1;

	return distS[G_loc];
}

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:304:13: warning: 'S_loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  304 |  distS[S_loc] = 0;
      |             ^
walk.cpp:332:16: warning: 'G_loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  332 |  if(distS[G_loc] >= INF)
      |                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 219396 KB Output is correct
2 Correct 110 ms 219448 KB Output is correct
3 Correct 114 ms 219592 KB Output is correct
4 Correct 111 ms 219436 KB Output is correct
5 Correct 109 ms 219464 KB Output is correct
6 Correct 110 ms 219480 KB Output is correct
7 Correct 114 ms 219540 KB Output is correct
8 Correct 114 ms 219456 KB Output is correct
9 Correct 109 ms 219472 KB Output is correct
10 Correct 112 ms 219456 KB Output is correct
11 Correct 117 ms 219408 KB Output is correct
12 Correct 118 ms 219552 KB Output is correct
13 Correct 109 ms 219460 KB Output is correct
14 Correct 110 ms 219460 KB Output is correct
15 Correct 109 ms 219412 KB Output is correct
16 Correct 116 ms 219416 KB Output is correct
17 Correct 120 ms 219584 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 219352 KB Output is correct
2 Correct 112 ms 219460 KB Output is correct
3 Correct 1575 ms 322704 KB Output is correct
4 Correct 1349 ms 340792 KB Output is correct
5 Correct 840 ms 315644 KB Output is correct
6 Correct 790 ms 307684 KB Output is correct
7 Correct 879 ms 315892 KB Output is correct
8 Correct 1624 ms 333548 KB Output is correct
9 Correct 1110 ms 329060 KB Output is correct
10 Correct 1473 ms 345152 KB Output is correct
11 Correct 1072 ms 304660 KB Output is correct
12 Correct 740 ms 290352 KB Output is correct
13 Correct 1450 ms 350932 KB Output is correct
14 Correct 658 ms 284644 KB Output is correct
15 Correct 714 ms 288108 KB Output is correct
16 Correct 703 ms 290624 KB Output is correct
17 Correct 669 ms 288136 KB Output is correct
18 Correct 1029 ms 290660 KB Output is correct
19 Correct 126 ms 222660 KB Output is correct
20 Correct 313 ms 251976 KB Output is correct
21 Correct 647 ms 285688 KB Output is correct
22 Correct 685 ms 289460 KB Output is correct
23 Correct 935 ms 299568 KB Output is correct
24 Correct 647 ms 289400 KB Output is correct
25 Correct 707 ms 287532 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 239224 KB Output is correct
2 Correct 2069 ms 356448 KB Output is correct
3 Correct 2137 ms 363012 KB Output is correct
4 Correct 2567 ms 379136 KB Output is correct
5 Correct 2880 ms 378028 KB Output is correct
6 Correct 2685 ms 373548 KB Output is correct
7 Correct 1048 ms 308964 KB Output is correct
8 Correct 721 ms 290352 KB Output is correct
9 Correct 2492 ms 368908 KB Output is correct
10 Correct 942 ms 306988 KB Output is correct
11 Correct 147 ms 227520 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 239224 KB Output is correct
2 Correct 2069 ms 356448 KB Output is correct
3 Correct 2137 ms 363012 KB Output is correct
4 Correct 2567 ms 379136 KB Output is correct
5 Correct 2880 ms 378028 KB Output is correct
6 Correct 2685 ms 373548 KB Output is correct
7 Correct 1048 ms 308964 KB Output is correct
8 Correct 721 ms 290352 KB Output is correct
9 Correct 2492 ms 368908 KB Output is correct
10 Correct 942 ms 306988 KB Output is correct
11 Correct 147 ms 227520 KB Output is correct
12 Correct 2412 ms 362512 KB Output is correct
13 Correct 1577 ms 379028 KB Output is correct
14 Correct 2825 ms 377940 KB Output is correct
15 Correct 1750 ms 343356 KB Output is correct
16 Correct 1645 ms 349800 KB Output is correct
17 Correct 1939 ms 377704 KB Output is correct
18 Correct 1725 ms 343340 KB Output is correct
19 Correct 1633 ms 349808 KB Output is correct
20 Correct 1121 ms 307368 KB Output is correct
21 Correct 185 ms 237116 KB Output is correct
22 Correct 1162 ms 343096 KB Output is correct
23 Correct 1018 ms 334412 KB Output is correct
24 Correct 765 ms 300240 KB Output is correct
25 Correct 929 ms 326308 KB Output is correct
26 Correct 621 ms 284556 KB Output is correct
27 Correct 2692 ms 378376 KB Output is correct
28 Correct 1465 ms 376828 KB Output is correct
29 Correct 2593 ms 373280 KB Output is correct
30 Correct 1050 ms 308520 KB Output is correct
31 Correct 2493 ms 368820 KB Output is correct
32 Correct 734 ms 293584 KB Output is correct
33 Correct 742 ms 295632 KB Output is correct
34 Correct 850 ms 300628 KB Output is correct
35 Correct 925 ms 310624 KB Output is correct
36 Correct 770 ms 296500 KB Output is correct
37 Correct 639 ms 285448 KB Output is correct
38 Correct 674 ms 289504 KB Output is correct
39 Correct 875 ms 299664 KB Output is correct
40 Correct 650 ms 289408 KB Output is correct
41 Correct 663 ms 287664 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 219396 KB Output is correct
2 Correct 110 ms 219448 KB Output is correct
3 Correct 114 ms 219592 KB Output is correct
4 Correct 111 ms 219436 KB Output is correct
5 Correct 109 ms 219464 KB Output is correct
6 Correct 110 ms 219480 KB Output is correct
7 Correct 114 ms 219540 KB Output is correct
8 Correct 114 ms 219456 KB Output is correct
9 Correct 109 ms 219472 KB Output is correct
10 Correct 112 ms 219456 KB Output is correct
11 Correct 117 ms 219408 KB Output is correct
12 Correct 118 ms 219552 KB Output is correct
13 Correct 109 ms 219460 KB Output is correct
14 Correct 110 ms 219460 KB Output is correct
15 Correct 109 ms 219412 KB Output is correct
16 Correct 116 ms 219416 KB Output is correct
17 Correct 120 ms 219584 KB Output is correct
18 Correct 112 ms 219352 KB Output is correct
19 Correct 112 ms 219460 KB Output is correct
20 Correct 1575 ms 322704 KB Output is correct
21 Correct 1349 ms 340792 KB Output is correct
22 Correct 840 ms 315644 KB Output is correct
23 Correct 790 ms 307684 KB Output is correct
24 Correct 879 ms 315892 KB Output is correct
25 Correct 1624 ms 333548 KB Output is correct
26 Correct 1110 ms 329060 KB Output is correct
27 Correct 1473 ms 345152 KB Output is correct
28 Correct 1072 ms 304660 KB Output is correct
29 Correct 740 ms 290352 KB Output is correct
30 Correct 1450 ms 350932 KB Output is correct
31 Correct 658 ms 284644 KB Output is correct
32 Correct 714 ms 288108 KB Output is correct
33 Correct 703 ms 290624 KB Output is correct
34 Correct 669 ms 288136 KB Output is correct
35 Correct 1029 ms 290660 KB Output is correct
36 Correct 126 ms 222660 KB Output is correct
37 Correct 313 ms 251976 KB Output is correct
38 Correct 647 ms 285688 KB Output is correct
39 Correct 685 ms 289460 KB Output is correct
40 Correct 935 ms 299568 KB Output is correct
41 Correct 647 ms 289400 KB Output is correct
42 Correct 707 ms 287532 KB Output is correct
43 Correct 322 ms 239224 KB Output is correct
44 Correct 2069 ms 356448 KB Output is correct
45 Correct 2137 ms 363012 KB Output is correct
46 Correct 2567 ms 379136 KB Output is correct
47 Correct 2880 ms 378028 KB Output is correct
48 Correct 2685 ms 373548 KB Output is correct
49 Correct 1048 ms 308964 KB Output is correct
50 Correct 721 ms 290352 KB Output is correct
51 Correct 2492 ms 368908 KB Output is correct
52 Correct 942 ms 306988 KB Output is correct
53 Correct 147 ms 227520 KB Output is correct
54 Correct 2412 ms 362512 KB Output is correct
55 Correct 1577 ms 379028 KB Output is correct
56 Correct 2825 ms 377940 KB Output is correct
57 Correct 1750 ms 343356 KB Output is correct
58 Correct 1645 ms 349800 KB Output is correct
59 Correct 1939 ms 377704 KB Output is correct
60 Correct 1725 ms 343340 KB Output is correct
61 Correct 1633 ms 349808 KB Output is correct
62 Correct 1121 ms 307368 KB Output is correct
63 Correct 185 ms 237116 KB Output is correct
64 Correct 1162 ms 343096 KB Output is correct
65 Correct 1018 ms 334412 KB Output is correct
66 Correct 765 ms 300240 KB Output is correct
67 Correct 929 ms 326308 KB Output is correct
68 Correct 621 ms 284556 KB Output is correct
69 Correct 2692 ms 378376 KB Output is correct
70 Correct 1465 ms 376828 KB Output is correct
71 Correct 2593 ms 373280 KB Output is correct
72 Correct 1050 ms 308520 KB Output is correct
73 Correct 2493 ms 368820 KB Output is correct
74 Correct 734 ms 293584 KB Output is correct
75 Correct 742 ms 295632 KB Output is correct
76 Correct 850 ms 300628 KB Output is correct
77 Correct 925 ms 310624 KB Output is correct
78 Correct 770 ms 296500 KB Output is correct
79 Correct 639 ms 285448 KB Output is correct
80 Correct 674 ms 289504 KB Output is correct
81 Correct 875 ms 299664 KB Output is correct
82 Correct 650 ms 289408 KB Output is correct
83 Correct 663 ms 287664 KB Output is correct
84 Correct 252 ms 236724 KB Output is correct
85 Correct 2467 ms 367220 KB Output is correct
86 Correct 3402 ms 411104 KB Output is correct
87 Correct 227 ms 245304 KB Output is correct
88 Correct 246 ms 246128 KB Output is correct
89 Correct 234 ms 245380 KB Output is correct
90 Correct 156 ms 227900 KB Output is correct
91 Correct 116 ms 219728 KB Output is correct
92 Correct 151 ms 225980 KB Output is correct
93 Correct 806 ms 284796 KB Output is correct
94 Correct 185 ms 237488 KB Output is correct
95 Correct 1233 ms 349244 KB Output is correct
96 Correct 1022 ms 335140 KB Output is correct
97 Correct 788 ms 300208 KB Output is correct
98 Correct 936 ms 326192 KB Output is correct
99 Execution timed out 4100 ms 443200 KB Time limit exceeded
100 Halted 0 ms 0 KB -