oj.uz

Submission #417181

# Submission time Handle Problem Language Result Execution time Memory
417181 2021-06-03T12:40:16 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
43 / 100
 2870 ms 284716 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];

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

		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:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   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:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   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:161:3: note: in expansion of macro 'DE'
  161 |   DE(x, d);
      |   ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 188100 KB Output is correct
2 Correct 110 ms 188100 KB Output is correct
3 Correct 112 ms 188096 KB Output is correct
4 Correct 109 ms 188072 KB Output is correct
5 Correct 114 ms 188148 KB Output is correct
6 Correct 113 ms 188196 KB Output is correct
7 Correct 110 ms 188128 KB Output is correct
8 Correct 111 ms 188172 KB Output is correct
9 Correct 110 ms 188112 KB Output is correct
10 Correct 112 ms 188212 KB Output is correct
11 Correct 110 ms 188100 KB Output is correct
12 Correct 112 ms 188108 KB Output is correct
13 Correct 113 ms 188104 KB Output is correct
14 Correct 112 ms 188168 KB Output is correct
15 Correct 111 ms 188120 KB Output is correct
16 Correct 112 ms 188100 KB Output is correct
17 Correct 110 ms 188188 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 188044 KB Output is correct
2 Correct 115 ms 188216 KB Output is correct
3 Correct 1116 ms 243624 KB Output is correct
4 Correct 1227 ms 246752 KB Output is correct
5 Correct 851 ms 230544 KB Output is correct
6 Correct 801 ms 226632 KB Output is correct
7 Correct 854 ms 230368 KB Output is correct
8 Correct 1304 ms 249496 KB Output is correct
9 Correct 1057 ms 237420 KB Output is correct
10 Incorrect 1333 ms 251016 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 195048 KB Output is correct
2 Correct 1910 ms 270296 KB Output is correct
3 Correct 2176 ms 275696 KB Output is correct
4 Correct 2388 ms 280664 KB Output is correct
5 Correct 2870 ms 284048 KB Output is correct
6 Correct 2564 ms 273312 KB Output is correct
7 Correct 1103 ms 237960 KB Output is correct
8 Correct 582 ms 215416 KB Output is correct
9 Correct 2297 ms 266664 KB Output is correct
10 Correct 650 ms 221336 KB Output is correct
11 Correct 128 ms 192324 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 195048 KB Output is correct
2 Correct 1910 ms 270296 KB Output is correct
3 Correct 2176 ms 275696 KB Output is correct
4 Correct 2388 ms 280664 KB Output is correct
5 Correct 2870 ms 284048 KB Output is correct
6 Correct 2564 ms 273312 KB Output is correct
7 Correct 1103 ms 237960 KB Output is correct
8 Correct 582 ms 215416 KB Output is correct
9 Correct 2297 ms 266664 KB Output is correct
10 Correct 650 ms 221336 KB Output is correct
11 Correct 128 ms 192324 KB Output is correct
12 Correct 2344 ms 275752 KB Output is correct
13 Correct 2198 ms 280828 KB Output is correct
14 Correct 2443 ms 284716 KB Output is correct
15 Correct 1413 ms 251120 KB Output is correct
16 Correct 1379 ms 255912 KB Output is correct
17 Correct 1615 ms 273608 KB Output is correct
18 Correct 1294 ms 251376 KB Output is correct
19 Correct 1351 ms 255724 KB Output is correct
20 Correct 1043 ms 236624 KB Output is correct
21 Correct 155 ms 195968 KB Output is correct
22 Correct 1257 ms 250748 KB Output is correct
23 Correct 1069 ms 244048 KB Output is correct
24 Correct 722 ms 222952 KB Output is correct
25 Correct 967 ms 239204 KB Output is correct
26 Correct 557 ms 215464 KB Output is correct
27 Correct 2264 ms 284372 KB Output is correct
28 Correct 1634 ms 278816 KB Output is correct
29 Correct 1970 ms 273744 KB Output is correct
30 Correct 903 ms 237584 KB Output is correct
31 Correct 1795 ms 266776 KB Output is correct
32 Correct 445 ms 215764 KB Output is correct
33 Correct 427 ms 215992 KB Output is correct
34 Correct 589 ms 219152 KB Output is correct
35 Correct 697 ms 225800 KB Output is correct
36 Correct 435 ms 214052 KB Output is correct
37 Correct 312 ms 207304 KB Output is correct
38 Correct 298 ms 206172 KB Output is correct
39 Correct 640 ms 217748 KB Output is correct
40 Correct 350 ms 208376 KB Output is correct
41 Correct 326 ms 208012 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 188100 KB Output is correct
2 Correct 110 ms 188100 KB Output is correct
3 Correct 112 ms 188096 KB Output is correct
4 Correct 109 ms 188072 KB Output is correct
5 Correct 114 ms 188148 KB Output is correct
6 Correct 113 ms 188196 KB Output is correct
7 Correct 110 ms 188128 KB Output is correct
8 Correct 111 ms 188172 KB Output is correct
9 Correct 110 ms 188112 KB Output is correct
10 Correct 112 ms 188212 KB Output is correct
11 Correct 110 ms 188100 KB Output is correct
12 Correct 112 ms 188108 KB Output is correct
13 Correct 113 ms 188104 KB Output is correct
14 Correct 112 ms 188168 KB Output is correct
15 Correct 111 ms 188120 KB Output is correct
16 Correct 112 ms 188100 KB Output is correct
17 Correct 110 ms 188188 KB Output is correct
18 Correct 111 ms 188044 KB Output is correct
19 Correct 115 ms 188216 KB Output is correct
20 Correct 1116 ms 243624 KB Output is correct
21 Correct 1227 ms 246752 KB Output is correct
22 Correct 851 ms 230544 KB Output is correct
23 Correct 801 ms 226632 KB Output is correct
24 Correct 854 ms 230368 KB Output is correct
25 Correct 1304 ms 249496 KB Output is correct
26 Correct 1057 ms 237420 KB Output is correct
27 Incorrect 1333 ms 251016 KB Output isn't correct
28 Halted 0 ms 0 KB -