oj.uz

Submission #417187

# Submission time Handle Problem Language Result Execution time Memory
417187 2021-06-03T12:45:43 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
43 / 100
 2459 ms 284480 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);

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 188056 KB Output is correct
2 Correct 104 ms 188104 KB Output is correct
3 Correct 101 ms 188100 KB Output is correct
4 Correct 100 ms 188100 KB Output is correct
5 Correct 98 ms 188104 KB Output is correct
6 Correct 101 ms 188132 KB Output is correct
7 Correct 102 ms 188100 KB Output is correct
8 Correct 100 ms 188068 KB Output is correct
9 Correct 101 ms 188152 KB Output is correct
10 Correct 105 ms 188120 KB Output is correct
11 Correct 104 ms 188120 KB Output is correct
12 Correct 103 ms 188084 KB Output is correct
13 Correct 99 ms 188100 KB Output is correct
14 Correct 100 ms 188084 KB Output is correct
15 Correct 101 ms 188108 KB Output is correct
16 Correct 99 ms 188144 KB Output is correct
17 Correct 103 ms 188084 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 188044 KB Output is correct
2 Correct 103 ms 188100 KB Output is correct
3 Correct 1022 ms 244100 KB Output is correct
4 Correct 1089 ms 247524 KB Output is correct
5 Correct 757 ms 231088 KB Output is correct
6 Correct 741 ms 227524 KB Output is correct
7 Correct 764 ms 231304 KB Output is correct
8 Correct 1138 ms 250388 KB Output is correct
9 Correct 958 ms 238348 KB Output is correct
10 Incorrect 1183 ms 251880 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 171 ms 195592 KB Output is correct
2 Correct 1767 ms 270684 KB Output is correct
3 Correct 1941 ms 276184 KB Output is correct
4 Correct 2140 ms 280928 KB Output is correct
5 Correct 2447 ms 284480 KB Output is correct
6 Correct 2074 ms 273048 KB Output is correct
7 Correct 1014 ms 237332 KB Output is correct
8 Correct 648 ms 214776 KB Output is correct
9 Correct 2277 ms 266140 KB Output is correct
10 Correct 592 ms 220708 KB Output is correct
11 Correct 123 ms 191684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 195592 KB Output is correct
2 Correct 1767 ms 270684 KB Output is correct
3 Correct 1941 ms 276184 KB Output is correct
4 Correct 2140 ms 280928 KB Output is correct
5 Correct 2447 ms 284480 KB Output is correct
6 Correct 2074 ms 273048 KB Output is correct
7 Correct 1014 ms 237332 KB Output is correct
8 Correct 648 ms 214776 KB Output is correct
9 Correct 2277 ms 266140 KB Output is correct
10 Correct 592 ms 220708 KB Output is correct
11 Correct 123 ms 191684 KB Output is correct
12 Correct 2061 ms 275180 KB Output is correct
13 Correct 1975 ms 280464 KB Output is correct
14 Correct 2379 ms 284004 KB Output is correct
15 Correct 1240 ms 250516 KB Output is correct
16 Correct 1264 ms 255268 KB Output is correct
17 Correct 1575 ms 272940 KB Output is correct
18 Correct 1278 ms 250476 KB Output is correct
19 Correct 1251 ms 255164 KB Output is correct
20 Correct 997 ms 235876 KB Output is correct
21 Correct 139 ms 195316 KB Output is correct
22 Correct 1224 ms 250140 KB Output is correct
23 Correct 1060 ms 243328 KB Output is correct
24 Correct 662 ms 222080 KB Output is correct
25 Correct 936 ms 238840 KB Output is correct
26 Correct 536 ms 214820 KB Output is correct
27 Correct 2393 ms 283744 KB Output is correct
28 Correct 1773 ms 278076 KB Output is correct
29 Correct 2459 ms 272852 KB Output is correct
30 Correct 1027 ms 236892 KB Output is correct
31 Correct 2213 ms 266116 KB Output is correct
32 Correct 457 ms 215028 KB Output is correct
33 Correct 429 ms 215604 KB Output is correct
34 Correct 567 ms 218452 KB Output is correct
35 Correct 684 ms 225208 KB Output is correct
36 Correct 450 ms 213308 KB Output is correct
37 Correct 303 ms 206664 KB Output is correct
38 Correct 298 ms 205520 KB Output is correct
39 Correct 631 ms 217176 KB Output is correct
40 Correct 351 ms 207984 KB Output is correct
41 Correct 329 ms 207524 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 188056 KB Output is correct
2 Correct 104 ms 188104 KB Output is correct
3 Correct 101 ms 188100 KB Output is correct
4 Correct 100 ms 188100 KB Output is correct
5 Correct 98 ms 188104 KB Output is correct
6 Correct 101 ms 188132 KB Output is correct
7 Correct 102 ms 188100 KB Output is correct
8 Correct 100 ms 188068 KB Output is correct
9 Correct 101 ms 188152 KB Output is correct
10 Correct 105 ms 188120 KB Output is correct
11 Correct 104 ms 188120 KB Output is correct
12 Correct 103 ms 188084 KB Output is correct
13 Correct 99 ms 188100 KB Output is correct
14 Correct 100 ms 188084 KB Output is correct
15 Correct 101 ms 188108 KB Output is correct
16 Correct 99 ms 188144 KB Output is correct
17 Correct 103 ms 188084 KB Output is correct
18 Correct 97 ms 188044 KB Output is correct
19 Correct 103 ms 188100 KB Output is correct
20 Correct 1022 ms 244100 KB Output is correct
21 Correct 1089 ms 247524 KB Output is correct
22 Correct 757 ms 231088 KB Output is correct
23 Correct 741 ms 227524 KB Output is correct
24 Correct 764 ms 231304 KB Output is correct
25 Correct 1138 ms 250388 KB Output is correct
26 Correct 958 ms 238348 KB Output is correct
27 Incorrect 1183 ms 251880 KB Output isn't correct
28 Halted 0 ms 0 KB -