oj.uz

Submission #417192

# Submission time Handle Problem Language Result Execution time Memory
417192 2021-06-03T12:48:02 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
100 / 100
 2465 ms 276812 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif


// TODO Watch out for the size
const int MAX_N = 400010 * 10;
const ll inf = 1ll << 55;
#include "walk.h"

// graph is 0 based
int n, m;
vector<int> xup[MAX_N];
vector<int> x, h, pfsz;
vector<pair<int,int>> edge[MAX_N];

int get_id(int i, int j) {
	assert(binary_search(AI(xup[i]), j));
	return lower_bound(AI(xup[i]), j) - begin(xup[i]) + pfsz[i];
}


const int C = MAX_N;

void sweep(vector<int> l, vector<int> r, vector<int> y) {
	set<int> ally;
	vector<vector<int>> in(n + 10), out(n + 10);
	for (int i = 0;i < m;++i) {
		if (r[i] - l[i] + 1 <= 2) continue;
		DE(l[i], r[i], y[i]);
		in[l[i]+1].pb(y[i]);
		out[r[i]].pb(y[i]);
	}

	for (int i = 0;i < n;++i) {
		for (int j : out[i]) ally.erase(j);
		for (int j : in[i]) ally.insert(j);

		vector<int> ep = xup[i];

		if (ep.size() && ep[0] == 0) {
			xup[i].insert(end(xup[i]), AI(ally));
			continue;
		}

//		auto it = begin(ally), rit = ally.upper_bound(h[i]);
//		for (int j = 0;j < C && it != rit;++j) {
//			xup[i].pb(*it++);
//		}
//		for (int j = 0;j < C && it != rit;++j)
//			xup[i].pb(*--rit);

		ep.pb(0), ep.pb(h[i]);
		for (int j : ep) {
			auto it = ally.upper_bound(j);
			{
				auto c = it;
				if (c != end(ally)) xup[i].pb(*c++);
				//if (c != end(ally)) xup[i].pb(*c++);
			}
			//if (it != begin(ally)) xup[i].pb(*prev(it)), --it;
			if (it != begin(ally)) xup[i].pb(*prev(it));
		}
	}
}
void init_ver(std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
//	for (int i = 0;i < m;++i) {
//		for (int j = l[i];j <= r[i];++j) {
//			if (h[j] < y[i]) continue;
//			xup[j].pb(y[i]);
//		}
//	}
//	for (int i = 0;i < n;++i) {
//		sort(AI(xup[i]));
//		xup[i].erase(unique(AI(xup[i])), end(xup[i]));
//		if (xup[i].size() < C * 2) continue;
//		vector<int> e(end(xup[i])-C, end(xup[i]));
//		xup[i].resize(C);
//		xup[i].insert(end(xup[i]), AI(e));
//	}
//

	xup[s].pb(0), xup[g].pb(0);

	for (int i = 0;i < m;++i) {
		xup[ l[i] ].pb( y[i] );
		xup[ r[i] ].pb( y[i] );
	}

	sweep(l, r, y);

	pfsz.resize(n+1);
	for (int i = 0;i < n;++i) {
		sort(AI(xup[i]));
		xup[i].erase(unique(AI(xup[i])), end(xup[i]));
		while (xup[i].size() && xup[i].back() > h[i])
			xup[i].pop_back();

		pfsz[i+1] = pfsz[i] + xup[i].size();
		for (int j = 1;j < xup[i].size();++j) {
			int a = pfsz[i]+j-1, b = pfsz[i] + j
			//int a = get_id(i, xup[i][j-1]), b = get_id(i, xup[i][j]),
				, d = xup[i][j] - xup[i][j-1];
			edge[a].pb(b, d);
			edge[b].pb(a, d);
		}
	}
}

void mbuild(vector<int> l, vector<int> r, vector<int> y) {

	map<int, vector<int>> xs;

	for (int i = 0;i < n;++i) {
		for (int j : xup[i])
			xs[j].pb(i);
	}

	for (int i = 0;i < m;++i) {
		vector< int > loc;

		auto it = lower_bound(AI( xs[y[i]] ), l[i]);
		while (it != end(xs[y[i]])) {
			if (*it > r[i]) break;
			loc.pb(*it++);
		}

		for (int j = 1;j < loc.size();++j) {
			int a = get_id(loc[j-1], y[i]), b = get_id(loc[j], y[i]),
				d = x[ loc[j] ] - x[ loc[j-1] ];
		
			edge[a].pb(b, d);
			edge[b].pb(a, d);
		}
	}
}

ll sho(int s, int t) {
	int V = pfsz.back() + 10;
	vector<ll> dis(V, inf);
	
	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
	auto upd = [&](int id, ll d) {
		if (chmin(dis[id], d))
			pq.emplace(d, id);
	};

	upd(s, 0);

	while (pq.size()) {
		auto [d, x] = pq.top(); pq.pop();
		if (d != dis[x]) continue;
		if (x == t) return d;
		DE(x, d);
		for (auto [u, w] : edge[x])
			upd(u, d + w);
	}
	return -1;

}

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 g) {
	n = x.size();
	m = l.size();
	::x = x;
	::h = h;

	init_ver(l, r, y, s, g);

	mbuild(l, r, y);

	return sho( get_id(s, 0), get_id(g, 0) );
}

Compilation message

walk.cpp: In function 'void sweep(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:43:3: note: in expansion of macro 'DE'
   43 |   DE(l[i], r[i], y[i]);
      |   ^~
walk.cpp: In function 'void init_ver(std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int j = 1;j < xup[i].size();++j) {
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp: In function 'void mbuild(std::vector<int>, std::vector<int>, std::vector<int>)':
walk.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for (int j = 1;j < loc.size();++j) {
      |                  ~~^~~~~~~~~~~~
walk.cpp: In function 'll sho(int, int)':
walk.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:167:3: note: in expansion of macro 'DE'
  167 |   DE(x, d);
      |   ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 188132 KB Output is correct
2 Correct 111 ms 188084 KB Output is correct
3 Correct 111 ms 188128 KB Output is correct
4 Correct 111 ms 188136 KB Output is correct
5 Correct 107 ms 188080 KB Output is correct
6 Correct 108 ms 188080 KB Output is correct
7 Correct 110 ms 188100 KB Output is correct
8 Correct 108 ms 188052 KB Output is correct
9 Correct 110 ms 188052 KB Output is correct
10 Correct 109 ms 188100 KB Output is correct
11 Correct 117 ms 188124 KB Output is correct
12 Correct 120 ms 188156 KB Output is correct
13 Correct 120 ms 188104 KB Output is correct
14 Correct 110 ms 188124 KB Output is correct
15 Correct 114 ms 188100 KB Output is correct
16 Correct 106 ms 188092 KB Output is correct
17 Correct 111 ms 188108 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 188108 KB Output is correct
2 Correct 112 ms 188064 KB Output is correct
3 Correct 1056 ms 234716 KB Output is correct
4 Correct 1311 ms 245220 KB Output is correct
5 Correct 927 ms 232572 KB Output is correct
6 Correct 922 ms 228744 KB Output is correct
7 Correct 939 ms 232628 KB Output is correct
8 Correct 1131 ms 237948 KB Output is correct
9 Correct 1138 ms 236444 KB Output is correct
10 Correct 1323 ms 249388 KB Output is correct
11 Correct 926 ms 225844 KB Output is correct
12 Correct 646 ms 215012 KB Output is correct
13 Correct 1444 ms 249084 KB Output is correct
14 Correct 647 ms 215476 KB Output is correct
15 Correct 599 ms 209808 KB Output is correct
16 Correct 472 ms 210752 KB Output is correct
17 Correct 471 ms 209580 KB Output is correct
18 Correct 709 ms 220708 KB Output is correct
19 Correct 114 ms 189648 KB Output is correct
20 Correct 238 ms 202364 KB Output is correct
21 Correct 388 ms 207476 KB Output is correct
22 Correct 359 ms 207812 KB Output is correct
23 Correct 800 ms 218540 KB Output is correct
24 Correct 451 ms 209560 KB Output is correct
25 Correct 402 ms 208428 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 195304 KB Output is correct
2 Correct 1492 ms 245208 KB Output is correct
3 Correct 1656 ms 248500 KB Output is correct
4 Correct 2119 ms 265604 KB Output is correct
5 Correct 2465 ms 271900 KB Output is correct
6 Correct 2257 ms 264228 KB Output is correct
7 Correct 1097 ms 238040 KB Output is correct
8 Correct 572 ms 216108 KB Output is correct
9 Correct 1991 ms 260144 KB Output is correct
10 Correct 730 ms 234960 KB Output is correct
11 Correct 146 ms 192620 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 195304 KB Output is correct
2 Correct 1492 ms 245208 KB Output is correct
3 Correct 1656 ms 248500 KB Output is correct
4 Correct 2119 ms 265604 KB Output is correct
5 Correct 2465 ms 271900 KB Output is correct
6 Correct 2257 ms 264228 KB Output is correct
7 Correct 1097 ms 238040 KB Output is correct
8 Correct 572 ms 216108 KB Output is correct
9 Correct 1991 ms 260144 KB Output is correct
10 Correct 730 ms 234960 KB Output is correct
11 Correct 146 ms 192620 KB Output is correct
12 Correct 1746 ms 249116 KB Output is correct
13 Correct 1931 ms 267340 KB Output is correct
14 Correct 2369 ms 271796 KB Output is correct
15 Correct 1140 ms 239956 KB Output is correct
16 Correct 1512 ms 253076 KB Output is correct
17 Correct 1558 ms 262104 KB Output is correct
18 Correct 1205 ms 239564 KB Output is correct
19 Correct 1519 ms 252692 KB Output is correct
20 Correct 1134 ms 238576 KB Output is correct
21 Correct 340 ms 210584 KB Output is correct
22 Correct 1128 ms 246196 KB Output is correct
23 Correct 999 ms 242152 KB Output is correct
24 Correct 762 ms 226008 KB Output is correct
25 Correct 1018 ms 239392 KB Output is correct
26 Correct 565 ms 215920 KB Output is correct
27 Correct 2454 ms 270808 KB Output is correct
28 Correct 1712 ms 266424 KB Output is correct
29 Correct 2077 ms 264560 KB Output is correct
30 Correct 1010 ms 238504 KB Output is correct
31 Correct 2013 ms 260936 KB Output is correct
32 Correct 530 ms 218884 KB Output is correct
33 Correct 539 ms 220980 KB Output is correct
34 Correct 719 ms 222468 KB Output is correct
35 Correct 788 ms 224676 KB Output is correct
36 Correct 553 ms 214648 KB Output is correct
37 Correct 360 ms 207096 KB Output is correct
38 Correct 348 ms 207548 KB Output is correct
39 Correct 818 ms 218168 KB Output is correct
40 Correct 430 ms 209412 KB Output is correct
41 Correct 420 ms 208212 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 188132 KB Output is correct
2 Correct 111 ms 188084 KB Output is correct
3 Correct 111 ms 188128 KB Output is correct
4 Correct 111 ms 188136 KB Output is correct
5 Correct 107 ms 188080 KB Output is correct
6 Correct 108 ms 188080 KB Output is correct
7 Correct 110 ms 188100 KB Output is correct
8 Correct 108 ms 188052 KB Output is correct
9 Correct 110 ms 188052 KB Output is correct
10 Correct 109 ms 188100 KB Output is correct
11 Correct 117 ms 188124 KB Output is correct
12 Correct 120 ms 188156 KB Output is correct
13 Correct 120 ms 188104 KB Output is correct
14 Correct 110 ms 188124 KB Output is correct
15 Correct 114 ms 188100 KB Output is correct
16 Correct 106 ms 188092 KB Output is correct
17 Correct 111 ms 188108 KB Output is correct
18 Correct 108 ms 188108 KB Output is correct
19 Correct 112 ms 188064 KB Output is correct
20 Correct 1056 ms 234716 KB Output is correct
21 Correct 1311 ms 245220 KB Output is correct
22 Correct 927 ms 232572 KB Output is correct
23 Correct 922 ms 228744 KB Output is correct
24 Correct 939 ms 232628 KB Output is correct
25 Correct 1131 ms 237948 KB Output is correct
26 Correct 1138 ms 236444 KB Output is correct
27 Correct 1323 ms 249388 KB Output is correct
28 Correct 926 ms 225844 KB Output is correct
29 Correct 646 ms 215012 KB Output is correct
30 Correct 1444 ms 249084 KB Output is correct
31 Correct 647 ms 215476 KB Output is correct
32 Correct 599 ms 209808 KB Output is correct
33 Correct 472 ms 210752 KB Output is correct
34 Correct 471 ms 209580 KB Output is correct
35 Correct 709 ms 220708 KB Output is correct
36 Correct 114 ms 189648 KB Output is correct
37 Correct 238 ms 202364 KB Output is correct
38 Correct 388 ms 207476 KB Output is correct
39 Correct 359 ms 207812 KB Output is correct
40 Correct 800 ms 218540 KB Output is correct
41 Correct 451 ms 209560 KB Output is correct
42 Correct 402 ms 208428 KB Output is correct
43 Correct 193 ms 195304 KB Output is correct
44 Correct 1492 ms 245208 KB Output is correct
45 Correct 1656 ms 248500 KB Output is correct
46 Correct 2119 ms 265604 KB Output is correct
47 Correct 2465 ms 271900 KB Output is correct
48 Correct 2257 ms 264228 KB Output is correct
49 Correct 1097 ms 238040 KB Output is correct
50 Correct 572 ms 216108 KB Output is correct
51 Correct 1991 ms 260144 KB Output is correct
52 Correct 730 ms 234960 KB Output is correct
53 Correct 146 ms 192620 KB Output is correct
54 Correct 1746 ms 249116 KB Output is correct
55 Correct 1931 ms 267340 KB Output is correct
56 Correct 2369 ms 271796 KB Output is correct
57 Correct 1140 ms 239956 KB Output is correct
58 Correct 1512 ms 253076 KB Output is correct
59 Correct 1558 ms 262104 KB Output is correct
60 Correct 1205 ms 239564 KB Output is correct
61 Correct 1519 ms 252692 KB Output is correct
62 Correct 1134 ms 238576 KB Output is correct
63 Correct 340 ms 210584 KB Output is correct
64 Correct 1128 ms 246196 KB Output is correct
65 Correct 999 ms 242152 KB Output is correct
66 Correct 762 ms 226008 KB Output is correct
67 Correct 1018 ms 239392 KB Output is correct
68 Correct 565 ms 215920 KB Output is correct
69 Correct 2454 ms 270808 KB Output is correct
70 Correct 1712 ms 266424 KB Output is correct
71 Correct 2077 ms 264560 KB Output is correct
72 Correct 1010 ms 238504 KB Output is correct
73 Correct 2013 ms 260936 KB Output is correct
74 Correct 530 ms 218884 KB Output is correct
75 Correct 539 ms 220980 KB Output is correct
76 Correct 719 ms 222468 KB Output is correct
77 Correct 788 ms 224676 KB Output is correct
78 Correct 553 ms 214648 KB Output is correct
79 Correct 360 ms 207096 KB Output is correct
80 Correct 348 ms 207548 KB Output is correct
81 Correct 818 ms 218168 KB Output is correct
82 Correct 430 ms 209412 KB Output is correct
83 Correct 420 ms 208212 KB Output is correct
84 Correct 179 ms 194108 KB Output is correct
85 Correct 1617 ms 248448 KB Output is correct
86 Correct 2422 ms 275512 KB Output is correct
87 Correct 276 ms 208924 KB Output is correct
88 Correct 317 ms 210968 KB Output is correct
89 Correct 280 ms 208924 KB Output is correct
90 Correct 147 ms 191580 KB Output is correct
91 Correct 120 ms 188352 KB Output is correct
92 Correct 142 ms 192168 KB Output is correct
93 Correct 771 ms 226656 KB Output is correct
94 Correct 305 ms 208780 KB Output is correct
95 Correct 1176 ms 247164 KB Output is correct
96 Correct 1043 ms 241196 KB Output is correct
97 Correct 777 ms 224764 KB Output is correct
98 Correct 904 ms 238016 KB Output is correct
99 Correct 1869 ms 276812 KB Output is correct
100 Correct 1598 ms 265764 KB Output is correct
101 Correct 1622 ms 266352 KB Output is correct
102 Correct 822 ms 237088 KB Output is correct
103 Correct 511 ms 219776 KB Output is correct
104 Correct 492 ms 221160 KB Output is correct
105 Correct 659 ms 224300 KB Output is correct
106 Correct 553 ms 220680 KB Output is correct
107 Correct 602 ms 214576 KB Output is correct
108 Correct 180 ms 194268 KB Output is correct
109 Correct 1454 ms 252148 KB Output is correct
110 Correct 1441 ms 258932 KB Output is correct
111 Correct 1367 ms 264072 KB Output is correct
112 Correct 673 ms 224740 KB Output is correct
113 Correct 592 ms 220740 KB Output is correct