oj.uz

Submission #417190

# Submission time Handle Problem Language Result Execution time Memory
417190 2021-06-03T12:47:10 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
100 / 100
 3780 ms 325120 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 101 ms 188092 KB Output is correct
2 Correct 100 ms 188140 KB Output is correct
3 Correct 101 ms 188088 KB Output is correct
4 Correct 98 ms 188096 KB Output is correct
5 Correct 102 ms 188100 KB Output is correct
6 Correct 104 ms 188152 KB Output is correct
7 Correct 99 ms 188104 KB Output is correct
8 Correct 97 ms 188148 KB Output is correct
9 Correct 99 ms 188128 KB Output is correct
10 Correct 100 ms 188104 KB Output is correct
11 Correct 99 ms 188108 KB Output is correct
12 Correct 100 ms 188100 KB Output is correct
13 Correct 100 ms 188120 KB Output is correct
14 Correct 101 ms 188076 KB Output is correct
15 Correct 97 ms 188188 KB Output is correct
16 Correct 101 ms 188088 KB Output is correct
17 Correct 103 ms 188100 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 188228 KB Output is correct
2 Correct 104 ms 188068 KB Output is correct
3 Correct 1004 ms 244288 KB Output is correct
4 Correct 1201 ms 256600 KB Output is correct
5 Correct 886 ms 241956 KB Output is correct
6 Correct 878 ms 236548 KB Output is correct
7 Correct 877 ms 241988 KB Output is correct
8 Correct 1111 ms 250812 KB Output is correct
9 Correct 1027 ms 244412 KB Output is correct
10 Correct 1391 ms 266220 KB Output is correct
11 Correct 790 ms 230844 KB Output is correct
12 Correct 492 ms 216504 KB Output is correct
13 Correct 1361 ms 265380 KB Output is correct
14 Correct 539 ms 219864 KB Output is correct
15 Correct 485 ms 214708 KB Output is correct
16 Correct 412 ms 214856 KB Output is correct
17 Correct 396 ms 213900 KB Output is correct
18 Correct 674 ms 222264 KB Output is correct
19 Correct 111 ms 189784 KB Output is correct
20 Correct 255 ms 205532 KB Output is correct
21 Correct 379 ms 209660 KB Output is correct
22 Correct 379 ms 210184 KB Output is correct
23 Correct 779 ms 223900 KB Output is correct
24 Correct 455 ms 212240 KB Output is correct
25 Correct 447 ms 211148 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 195004 KB Output is correct
2 Correct 1912 ms 270440 KB Output is correct
3 Correct 2272 ms 278816 KB Output is correct
4 Correct 2691 ms 310348 KB Output is correct
5 Correct 3036 ms 315684 KB Output is correct
6 Correct 2588 ms 302304 KB Output is correct
7 Correct 1388 ms 266852 KB Output is correct
8 Correct 488 ms 214772 KB Output is correct
9 Correct 2503 ms 294828 KB Output is correct
10 Correct 782 ms 248892 KB Output is correct
11 Correct 117 ms 191720 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 195004 KB Output is correct
2 Correct 1912 ms 270440 KB Output is correct
3 Correct 2272 ms 278816 KB Output is correct
4 Correct 2691 ms 310348 KB Output is correct
5 Correct 3036 ms 315684 KB Output is correct
6 Correct 2588 ms 302304 KB Output is correct
7 Correct 1388 ms 266852 KB Output is correct
8 Correct 488 ms 214772 KB Output is correct
9 Correct 2503 ms 294828 KB Output is correct
10 Correct 782 ms 248892 KB Output is correct
11 Correct 117 ms 191720 KB Output is correct
12 Correct 2050 ms 278220 KB Output is correct
13 Correct 2521 ms 310336 KB Output is correct
14 Correct 3600 ms 314108 KB Output is correct
15 Correct 1627 ms 263680 KB Output is correct
16 Correct 2273 ms 287112 KB Output is correct
17 Correct 2697 ms 304908 KB Output is correct
18 Correct 1705 ms 263632 KB Output is correct
19 Correct 2392 ms 286784 KB Output is correct
20 Correct 1814 ms 266644 KB Output is correct
21 Correct 566 ms 224660 KB Output is correct
22 Correct 1794 ms 275620 KB Output is correct
23 Correct 1527 ms 264720 KB Output is correct
24 Correct 950 ms 230956 KB Output is correct
25 Correct 1500 ms 256820 KB Output is correct
26 Correct 650 ms 217640 KB Output is correct
27 Correct 3780 ms 314508 KB Output is correct
28 Correct 2511 ms 307764 KB Output is correct
29 Correct 3424 ms 305124 KB Output is correct
30 Correct 1746 ms 266960 KB Output is correct
31 Correct 3353 ms 297180 KB Output is correct
32 Correct 716 ms 228296 KB Output is correct
33 Correct 619 ms 230744 KB Output is correct
34 Correct 793 ms 233460 KB Output is correct
35 Correct 1020 ms 238612 KB Output is correct
36 Correct 629 ms 217388 KB Output is correct
37 Correct 416 ms 208584 KB Output is correct
38 Correct 404 ms 209004 KB Output is correct
39 Correct 829 ms 222644 KB Output is correct
40 Correct 464 ms 211092 KB Output is correct
41 Correct 422 ms 210004 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 188092 KB Output is correct
2 Correct 100 ms 188140 KB Output is correct
3 Correct 101 ms 188088 KB Output is correct
4 Correct 98 ms 188096 KB Output is correct
5 Correct 102 ms 188100 KB Output is correct
6 Correct 104 ms 188152 KB Output is correct
7 Correct 99 ms 188104 KB Output is correct
8 Correct 97 ms 188148 KB Output is correct
9 Correct 99 ms 188128 KB Output is correct
10 Correct 100 ms 188104 KB Output is correct
11 Correct 99 ms 188108 KB Output is correct
12 Correct 100 ms 188100 KB Output is correct
13 Correct 100 ms 188120 KB Output is correct
14 Correct 101 ms 188076 KB Output is correct
15 Correct 97 ms 188188 KB Output is correct
16 Correct 101 ms 188088 KB Output is correct
17 Correct 103 ms 188100 KB Output is correct
18 Correct 101 ms 188228 KB Output is correct
19 Correct 104 ms 188068 KB Output is correct
20 Correct 1004 ms 244288 KB Output is correct
21 Correct 1201 ms 256600 KB Output is correct
22 Correct 886 ms 241956 KB Output is correct
23 Correct 878 ms 236548 KB Output is correct
24 Correct 877 ms 241988 KB Output is correct
25 Correct 1111 ms 250812 KB Output is correct
26 Correct 1027 ms 244412 KB Output is correct
27 Correct 1391 ms 266220 KB Output is correct
28 Correct 790 ms 230844 KB Output is correct
29 Correct 492 ms 216504 KB Output is correct
30 Correct 1361 ms 265380 KB Output is correct
31 Correct 539 ms 219864 KB Output is correct
32 Correct 485 ms 214708 KB Output is correct
33 Correct 412 ms 214856 KB Output is correct
34 Correct 396 ms 213900 KB Output is correct
35 Correct 674 ms 222264 KB Output is correct
36 Correct 111 ms 189784 KB Output is correct
37 Correct 255 ms 205532 KB Output is correct
38 Correct 379 ms 209660 KB Output is correct
39 Correct 379 ms 210184 KB Output is correct
40 Correct 779 ms 223900 KB Output is correct
41 Correct 455 ms 212240 KB Output is correct
42 Correct 447 ms 211148 KB Output is correct
43 Correct 199 ms 195004 KB Output is correct
44 Correct 1912 ms 270440 KB Output is correct
45 Correct 2272 ms 278816 KB Output is correct
46 Correct 2691 ms 310348 KB Output is correct
47 Correct 3036 ms 315684 KB Output is correct
48 Correct 2588 ms 302304 KB Output is correct
49 Correct 1388 ms 266852 KB Output is correct
50 Correct 488 ms 214772 KB Output is correct
51 Correct 2503 ms 294828 KB Output is correct
52 Correct 782 ms 248892 KB Output is correct
53 Correct 117 ms 191720 KB Output is correct
54 Correct 2050 ms 278220 KB Output is correct
55 Correct 2521 ms 310336 KB Output is correct
56 Correct 3600 ms 314108 KB Output is correct
57 Correct 1627 ms 263680 KB Output is correct
58 Correct 2273 ms 287112 KB Output is correct
59 Correct 2697 ms 304908 KB Output is correct
60 Correct 1705 ms 263632 KB Output is correct
61 Correct 2392 ms 286784 KB Output is correct
62 Correct 1814 ms 266644 KB Output is correct
63 Correct 566 ms 224660 KB Output is correct
64 Correct 1794 ms 275620 KB Output is correct
65 Correct 1527 ms 264720 KB Output is correct
66 Correct 950 ms 230956 KB Output is correct
67 Correct 1500 ms 256820 KB Output is correct
68 Correct 650 ms 217640 KB Output is correct
69 Correct 3780 ms 314508 KB Output is correct
70 Correct 2511 ms 307764 KB Output is correct
71 Correct 3424 ms 305124 KB Output is correct
72 Correct 1746 ms 266960 KB Output is correct
73 Correct 3353 ms 297180 KB Output is correct
74 Correct 716 ms 228296 KB Output is correct
75 Correct 619 ms 230744 KB Output is correct
76 Correct 793 ms 233460 KB Output is correct
77 Correct 1020 ms 238612 KB Output is correct
78 Correct 629 ms 217388 KB Output is correct
79 Correct 416 ms 208584 KB Output is correct
80 Correct 404 ms 209004 KB Output is correct
81 Correct 829 ms 222644 KB Output is correct
82 Correct 464 ms 211092 KB Output is correct
83 Correct 422 ms 210004 KB Output is correct
84 Correct 203 ms 195452 KB Output is correct
85 Correct 2374 ms 280660 KB Output is correct
86 Correct 3360 ms 324192 KB Output is correct
87 Correct 365 ms 226008 KB Output is correct
88 Correct 453 ms 229540 KB Output is correct
89 Correct 363 ms 225896 KB Output is correct
90 Correct 153 ms 192780 KB Output is correct
91 Correct 135 ms 188504 KB Output is correct
92 Correct 176 ms 194840 KB Output is correct
93 Correct 1168 ms 254776 KB Output is correct
94 Correct 422 ms 225676 KB Output is correct
95 Correct 1730 ms 282756 KB Output is correct
96 Correct 1453 ms 268424 KB Output is correct
97 Correct 826 ms 234620 KB Output is correct
98 Correct 1262 ms 260176 KB Output is correct
99 Correct 3331 ms 325120 KB Output is correct
100 Correct 2789 ms 313092 KB Output is correct
101 Correct 2932 ms 311244 KB Output is correct
102 Correct 1339 ms 269856 KB Output is correct
103 Correct 628 ms 231292 KB Output is correct
104 Correct 607 ms 234348 KB Output is correct
105 Correct 798 ms 237356 KB Output is correct
106 Correct 677 ms 232748 KB Output is correct
107 Correct 672 ms 220508 KB Output is correct
108 Correct 241 ms 197928 KB Output is correct
109 Correct 2721 ms 291224 KB Output is correct
110 Correct 2571 ms 312580 KB Output is correct
111 Correct 2392 ms 301108 KB Output is correct
112 Correct 940 ms 240832 KB Output is correct
113 Correct 780 ms 233060 KB Output is correct