oj.uz

Submission #143099

# Submission time Handle Problem Language Result Execution time Memory
143099 2019-08-13T01:28:42 Z model_code Sky Walking (IOI19_walk) C++17
100 / 100
 1158 ms 167508 KB 
// model_solution/akm-full.cpp

#include "walk.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>

using namespace std;

const int MAXN = 200 * 1000 + 10;
const int MAXM = 200 * 1000 + 10;
const int MAXRM = 5 * MAXM;
const int MAXV = 2 * 2 * MAXRM;
const long long INF = 1000ll * 1000 * 1000 * 1000 * 1000 * 1000;

typedef pair<int, int> pii;
typedef set<pii>::iterator sit;

typedef pair<long long, int> pli;
long long dist[MAXV];

int vcnt = 0;
vector<pii> edges[MAXV];
set<pli> dij;
int last_x[MAXRM];
int last_vertex[MAXRM];
int last_height[MAXN];
int first_height[MAXN];
vector<pii> adds[MAXN];
vector<pii> removes[MAXN];
set<pii> walks;

long long dijkstra(int start, int dest)
{
	for (int i = 0; i < vcnt; i++)
		dist[i] = INF;
	dist[start] = 0;
	dij.insert(pli(dist[start], start));
	while (!dij.empty())
	{
		int v = dij.begin()->second;
		dij.erase(dij.begin());
		if (v == dest)
			return dist[v];
		for (int i = 0; i < (int)edges[v].size(); i++)
		{
			int u = edges[v][i].first;
			int w = edges[v][i].second;
			if (dist[u] > dist[v] + w)
			{
				dij.erase(pli(dist[u], u));
				dist[u] = dist[v] + w;
				dij.insert(pli(dist[u], u));
			}
		}
	}
	return -1;
}

void add_edge(int u, int v, int w)
{
	edges[u].push_back(pii(v, w));
	edges[v].push_back(pii(u, w));
}

int make_vertex(int walk, int x)
{
	if (last_x[walk] == x)
		return last_vertex[walk];
	int cur = vcnt++;
	if (last_vertex[walk] != -1)
		add_edge(last_vertex[walk], cur, x - last_x[walk]);
	last_x[walk] = x;
	last_vertex[walk] = cur;
	return cur;
}

void break_segments(vector<int> &l, vector<int> &r, vector<int> &y, int s, vector<int> &h)
{
	vector<int> heights = h;
	sort(heights.begin(), heights.end());
	heights.resize(unique(heights.begin(), heights.end()) - heights.begin());
	for (int i = 0; i < (int)heights.size(); i++)
	{
		last_height[i] = -1;
		first_height[i] = h.size() + 1;
	}
	for (int i = 0; i < (int)h.size(); i++)
	{
		int idx = lower_bound(heights.begin(), heights.end(), h[i]) - heights.begin();
		assert(idx < (int)heights.size());
		if (i <= s)
			last_height[idx] = max(last_height[idx], i);
		if (i >= s)
			first_height[idx] = min(first_height[idx], i);
	}
	for (int i = (int)heights.size() - 2; i >= 0; i--)
	{
		last_height[i] = max(last_height[i], last_height[i + 1]);
		first_height[i] = min(first_height[i], first_height[i + 1]);
	}
	for (int i = 0; i < (int)l.size(); i++)
		if (l[i] < s && r[i] > s)
		{
			int idx = lower_bound(heights.begin(), heights.end(), y[i]) - heights.begin();
			assert(idx < (int)heights.size());
			int x = l[i];
			int a = last_height[idx];
			int b = first_height[idx];
			int q = r[i];

			assert(a != -1);
			assert(b != (int)h.size() + 1);

			if (x < a)
			{
				r[i] = a;
				if (a < b)
				{
					l.push_back(a);
					r.push_back(b);
					y.push_back(y[i]);
				}
			}
			else
			{
				assert(x == a);
				r[i] = b;
			}
			if (q > b)
			{
				l.push_back(b);
				r.push_back(q);
				y.push_back(y[i]);
			}
			else
			{
				assert(q == b);
			}
		}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
	if (s == g)
		return 0;
	int n = x.size();

	break_segments(l, r, y, s, h);
	break_segments(l, r, y, g, h);
	int m = l.size();

	for (int i = 0; i < m; i++)
	{
		last_x[i] = last_vertex[i] = -1;
		adds[l[i]].push_back(pii(y[i], i));
		removes[r[i]].push_back(pii(y[i], i));
	}
	int sv = -1, gv = -1;
	long long res = 0;
	for (int i = 0; i < n; i++)
	{
		sort(adds[i].begin(), adds[i].end());
		for (int j = 0; j < (int)adds[i].size(); j++)
		{
			int v = make_vertex(adds[i][j].second, x[i]);
			sit it = walks.lower_bound(adds[i][j]);
			if (it != walks.begin())
			{
				it--;
				int u = make_vertex(it->second, x[i]);
				add_edge(u, v, adds[i][j].first - it->first);
			}
			walks.insert(adds[i][j]);
		}
		if (i == s)
		{
			if (walks.empty() || walks.begin()->first > h[i])
				return -1;
			sv = make_vertex(walks.begin()->second, x[i]);
			res += walks.begin()->first;
		}
		if (i == g)
		{
			if (walks.empty() || walks.begin()->first > h[i])
				return -1;
			gv = make_vertex(walks.begin()->second, x[i]);
			res += walks.begin()->first;
		}
		sort(removes[i].begin(), removes[i].end(), greater<pii>());
		for (int j = 0; j < (int)removes[i].size(); j++)
		{
			int v = make_vertex(removes[i][j].second, x[i]);
			sit it = walks.find(removes[i][j]);
			if (it != walks.begin())
			{
				sit it2 = it;
				it2--;
				int u = make_vertex(it2->second, x[i]);
				add_edge(u, v, removes[i][j].first - it2->first);
			}
			assert(it != walks.end());
			walks.erase(it);
		}
	}
	assert(sv != -1);
	assert(gv != -1);
	long long dij_res = dijkstra(sv, gv);
	if(dij_res == -1)
		return -1;
	return res + dij_res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 103672 KB Output is correct
2 Correct 95 ms 103672 KB Output is correct
3 Correct 95 ms 103672 KB Output is correct
4 Correct 95 ms 103676 KB Output is correct
5 Correct 96 ms 103672 KB Output is correct
6 Correct 94 ms 103672 KB Output is correct
7 Correct 94 ms 103672 KB Output is correct
8 Correct 95 ms 103748 KB Output is correct
9 Correct 95 ms 103692 KB Output is correct
10 Correct 105 ms 103736 KB Output is correct
11 Correct 111 ms 103672 KB Output is correct
12 Correct 96 ms 103672 KB Output is correct
13 Correct 94 ms 103612 KB Output is correct
14 Correct 94 ms 103800 KB Output is correct
15 Correct 96 ms 103672 KB Output is correct
16 Correct 94 ms 103672 KB Output is correct
17 Correct 96 ms 103712 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 103720 KB Output is correct
2 Correct 94 ms 103672 KB Output is correct
3 Correct 276 ms 125664 KB Output is correct
4 Correct 441 ms 130496 KB Output is correct
5 Correct 319 ms 123536 KB Output is correct
6 Correct 323 ms 122480 KB Output is correct
7 Correct 307 ms 123632 KB Output is correct
8 Correct 291 ms 126280 KB Output is correct
9 Correct 346 ms 127524 KB Output is correct
10 Correct 431 ms 129496 KB Output is correct
11 Correct 303 ms 124296 KB Output is correct
12 Correct 323 ms 123248 KB Output is correct
13 Correct 423 ms 132076 KB Output is correct
14 Correct 278 ms 116564 KB Output is correct
15 Correct 323 ms 121928 KB Output is correct
16 Correct 290 ms 122804 KB Output is correct
17 Correct 285 ms 122196 KB Output is correct
18 Correct 373 ms 130404 KB Output is correct
19 Correct 103 ms 104568 KB Output is correct
20 Correct 217 ms 112400 KB Output is correct
21 Correct 260 ms 121268 KB Output is correct
22 Correct 249 ms 122480 KB Output is correct
23 Correct 441 ms 126720 KB Output is correct
24 Correct 286 ms 122544 KB Output is correct
25 Correct 305 ms 122028 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 112148 KB Output is correct
2 Correct 417 ms 127700 KB Output is correct
3 Correct 509 ms 128596 KB Output is correct
4 Correct 572 ms 131788 KB Output is correct
5 Correct 741 ms 133712 KB Output is correct
6 Correct 700 ms 133348 KB Output is correct
7 Correct 310 ms 119280 KB Output is correct
8 Correct 284 ms 122480 KB Output is correct
9 Correct 639 ms 134084 KB Output is correct
10 Correct 296 ms 124140 KB Output is correct
11 Correct 112 ms 104696 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 112148 KB Output is correct
2 Correct 417 ms 127700 KB Output is correct
3 Correct 509 ms 128596 KB Output is correct
4 Correct 572 ms 131788 KB Output is correct
5 Correct 741 ms 133712 KB Output is correct
6 Correct 700 ms 133348 KB Output is correct
7 Correct 310 ms 119280 KB Output is correct
8 Correct 284 ms 122480 KB Output is correct
9 Correct 639 ms 134084 KB Output is correct
10 Correct 296 ms 124140 KB Output is correct
11 Correct 112 ms 104696 KB Output is correct
12 Correct 518 ms 128792 KB Output is correct
13 Correct 264 ms 113520 KB Output is correct
14 Correct 771 ms 135408 KB Output is correct
15 Correct 466 ms 127996 KB Output is correct
16 Correct 525 ms 129400 KB Output is correct
17 Correct 623 ms 132500 KB Output is correct
18 Correct 453 ms 128104 KB Output is correct
19 Correct 402 ms 126420 KB Output is correct
20 Correct 379 ms 120056 KB Output is correct
21 Correct 182 ms 106488 KB Output is correct
22 Correct 339 ms 126576 KB Output is correct
23 Correct 343 ms 126292 KB Output is correct
24 Correct 317 ms 122480 KB Output is correct
25 Correct 322 ms 125040 KB Output is correct
26 Correct 316 ms 118996 KB Output is correct
27 Correct 747 ms 135172 KB Output is correct
28 Correct 255 ms 113392 KB Output is correct
29 Correct 747 ms 134156 KB Output is correct
30 Correct 365 ms 120184 KB Output is correct
31 Correct 675 ms 134364 KB Output is correct
32 Correct 281 ms 122276 KB Output is correct
33 Correct 278 ms 122944 KB Output is correct
34 Correct 354 ms 124268 KB Output is correct
35 Correct 335 ms 124488 KB Output is correct
36 Correct 301 ms 122996 KB Output is correct
37 Correct 256 ms 121296 KB Output is correct
38 Correct 261 ms 122416 KB Output is correct
39 Correct 418 ms 126848 KB Output is correct
40 Correct 283 ms 122552 KB Output is correct
41 Correct 272 ms 122020 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 103672 KB Output is correct
2 Correct 95 ms 103672 KB Output is correct
3 Correct 95 ms 103672 KB Output is correct
4 Correct 95 ms 103676 KB Output is correct
5 Correct 96 ms 103672 KB Output is correct
6 Correct 94 ms 103672 KB Output is correct
7 Correct 94 ms 103672 KB Output is correct
8 Correct 95 ms 103748 KB Output is correct
9 Correct 95 ms 103692 KB Output is correct
10 Correct 105 ms 103736 KB Output is correct
11 Correct 111 ms 103672 KB Output is correct
12 Correct 96 ms 103672 KB Output is correct
13 Correct 94 ms 103612 KB Output is correct
14 Correct 94 ms 103800 KB Output is correct
15 Correct 96 ms 103672 KB Output is correct
16 Correct 94 ms 103672 KB Output is correct
17 Correct 96 ms 103712 KB Output is correct
18 Correct 95 ms 103720 KB Output is correct
19 Correct 94 ms 103672 KB Output is correct
20 Correct 276 ms 125664 KB Output is correct
21 Correct 441 ms 130496 KB Output is correct
22 Correct 319 ms 123536 KB Output is correct
23 Correct 323 ms 122480 KB Output is correct
24 Correct 307 ms 123632 KB Output is correct
25 Correct 291 ms 126280 KB Output is correct
26 Correct 346 ms 127524 KB Output is correct
27 Correct 431 ms 129496 KB Output is correct
28 Correct 303 ms 124296 KB Output is correct
29 Correct 323 ms 123248 KB Output is correct
30 Correct 423 ms 132076 KB Output is correct
31 Correct 278 ms 116564 KB Output is correct
32 Correct 323 ms 121928 KB Output is correct
33 Correct 290 ms 122804 KB Output is correct
34 Correct 285 ms 122196 KB Output is correct
35 Correct 373 ms 130404 KB Output is correct
36 Correct 103 ms 104568 KB Output is correct
37 Correct 217 ms 112400 KB Output is correct
38 Correct 260 ms 121268 KB Output is correct
39 Correct 249 ms 122480 KB Output is correct
40 Correct 441 ms 126720 KB Output is correct
41 Correct 286 ms 122544 KB Output is correct
42 Correct 305 ms 122028 KB Output is correct
43 Correct 170 ms 112148 KB Output is correct
44 Correct 417 ms 127700 KB Output is correct
45 Correct 509 ms 128596 KB Output is correct
46 Correct 572 ms 131788 KB Output is correct
47 Correct 741 ms 133712 KB Output is correct
48 Correct 700 ms 133348 KB Output is correct
49 Correct 310 ms 119280 KB Output is correct
50 Correct 284 ms 122480 KB Output is correct
51 Correct 639 ms 134084 KB Output is correct
52 Correct 296 ms 124140 KB Output is correct
53 Correct 112 ms 104696 KB Output is correct
54 Correct 518 ms 128792 KB Output is correct
55 Correct 264 ms 113520 KB Output is correct
56 Correct 771 ms 135408 KB Output is correct
57 Correct 466 ms 127996 KB Output is correct
58 Correct 525 ms 129400 KB Output is correct
59 Correct 623 ms 132500 KB Output is correct
60 Correct 453 ms 128104 KB Output is correct
61 Correct 402 ms 126420 KB Output is correct
62 Correct 379 ms 120056 KB Output is correct
63 Correct 182 ms 106488 KB Output is correct
64 Correct 339 ms 126576 KB Output is correct
65 Correct 343 ms 126292 KB Output is correct
66 Correct 317 ms 122480 KB Output is correct
67 Correct 322 ms 125040 KB Output is correct
68 Correct 316 ms 118996 KB Output is correct
69 Correct 747 ms 135172 KB Output is correct
70 Correct 255 ms 113392 KB Output is correct
71 Correct 747 ms 134156 KB Output is correct
72 Correct 365 ms 120184 KB Output is correct
73 Correct 675 ms 134364 KB Output is correct
74 Correct 281 ms 122276 KB Output is correct
75 Correct 278 ms 122944 KB Output is correct
76 Correct 354 ms 124268 KB Output is correct
77 Correct 335 ms 124488 KB Output is correct
78 Correct 301 ms 122996 KB Output is correct
79 Correct 256 ms 121296 KB Output is correct
80 Correct 261 ms 122416 KB Output is correct
81 Correct 418 ms 126848 KB Output is correct
82 Correct 283 ms 122552 KB Output is correct
83 Correct 272 ms 122020 KB Output is correct
84 Correct 158 ms 110328 KB Output is correct
85 Correct 470 ms 130672 KB Output is correct
86 Correct 1026 ms 150380 KB Output is correct
87 Correct 148 ms 107344 KB Output is correct
88 Correct 194 ms 108272 KB Output is correct
89 Correct 148 ms 107344 KB Output is correct
90 Correct 116 ms 105976 KB Output is correct
91 Correct 96 ms 103728 KB Output is correct
92 Correct 111 ms 104952 KB Output is correct
93 Correct 282 ms 115912 KB Output is correct
94 Correct 185 ms 106608 KB Output is correct
95 Correct 353 ms 127684 KB Output is correct
96 Correct 339 ms 126504 KB Output is correct
97 Correct 340 ms 122480 KB Output is correct
98 Correct 344 ms 124916 KB Output is correct
99 Correct 1158 ms 167508 KB Output is correct
100 Correct 536 ms 132504 KB Output is correct
101 Correct 721 ms 143476 KB Output is correct
102 Correct 313 ms 120348 KB Output is correct
103 Correct 282 ms 122400 KB Output is correct
104 Correct 278 ms 122996 KB Output is correct
105 Correct 325 ms 124636 KB Output is correct
106 Correct 328 ms 122608 KB Output is correct
107 Correct 343 ms 124656 KB Output is correct
108 Correct 128 ms 105976 KB Output is correct
109 Correct 616 ms 127856 KB Output is correct
110 Correct 297 ms 117268 KB Output is correct
111 Correct 320 ms 119772 KB Output is correct
112 Correct 325 ms 124164 KB Output is correct
113 Correct 315 ms 123532 KB Output is correct