oj.uz

Submission #417172

# Submission time Handle Problem Language Result Execution time Memory
417172 2021-06-03T12:35:35 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
43 / 100
 1798 ms 257852 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);
			if (it != end(ally)) xup[i].pb(*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:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   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:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   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:156:3: note: in expansion of macro 'DE'
  156 |   DE(x, d);
      |   ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 188100 KB Output is correct
2 Correct 113 ms 188036 KB Output is correct
3 Correct 117 ms 188060 KB Output is correct
4 Correct 112 ms 188100 KB Output is correct
5 Correct 109 ms 188168 KB Output is correct
6 Correct 111 ms 188180 KB Output is correct
7 Correct 110 ms 188100 KB Output is correct
8 Correct 109 ms 188148 KB Output is correct
9 Correct 111 ms 188080 KB Output is correct
10 Correct 111 ms 188164 KB Output is correct
11 Correct 110 ms 188060 KB Output is correct
12 Correct 111 ms 188148 KB Output is correct
13 Correct 111 ms 188160 KB Output is correct
14 Correct 118 ms 188092 KB Output is correct
15 Correct 117 ms 188120 KB Output is correct
16 Correct 124 ms 188100 KB Output is correct
17 Correct 114 ms 188048 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 188056 KB Output is correct
2 Correct 111 ms 188100 KB Output is correct
3 Correct 1116 ms 235408 KB Output is correct
4 Correct 1232 ms 234812 KB Output is correct
5 Correct 789 ms 224400 KB Output is correct
6 Correct 734 ms 221832 KB Output is correct
7 Correct 754 ms 224672 KB Output is correct
8 Correct 1050 ms 237712 KB Output is correct
9 Correct 921 ms 231776 KB Output is correct
10 Incorrect 1155 ms 239880 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 193 ms 195520 KB Output is correct
2 Correct 1342 ms 246472 KB Output is correct
3 Correct 1621 ms 248368 KB Output is correct
4 Correct 1729 ms 254548 KB Output is correct
5 Correct 1736 ms 257852 KB Output is correct
6 Correct 1493 ms 250740 KB Output is correct
7 Correct 758 ms 224884 KB Output is correct
8 Correct 544 ms 218936 KB Output is correct
9 Correct 1445 ms 247316 KB Output is correct
10 Correct 543 ms 219288 KB Output is correct
11 Correct 131 ms 192440 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 195520 KB Output is correct
2 Correct 1342 ms 246472 KB Output is correct
3 Correct 1621 ms 248368 KB Output is correct
4 Correct 1729 ms 254548 KB Output is correct
5 Correct 1736 ms 257852 KB Output is correct
6 Correct 1493 ms 250740 KB Output is correct
7 Correct 758 ms 224884 KB Output is correct
8 Correct 544 ms 218936 KB Output is correct
9 Correct 1445 ms 247316 KB Output is correct
10 Correct 543 ms 219288 KB Output is correct
11 Correct 131 ms 192440 KB Output is correct
12 Correct 1371 ms 248176 KB Output is correct
13 Correct 1361 ms 254476 KB Output is correct
14 Correct 1658 ms 257820 KB Output is correct
15 Correct 949 ms 234244 KB Output is correct
16 Correct 975 ms 238996 KB Output is correct
17 Correct 1109 ms 248000 KB Output is correct
18 Correct 933 ms 234364 KB Output is correct
19 Correct 970 ms 239088 KB Output is correct
20 Correct 732 ms 223596 KB Output is correct
21 Correct 156 ms 197320 KB Output is correct
22 Correct 912 ms 235664 KB Output is correct
23 Correct 852 ms 233144 KB Output is correct
24 Correct 647 ms 222260 KB Output is correct
25 Correct 805 ms 231292 KB Output is correct
26 Correct 537 ms 217132 KB Output is correct
27 Correct 1668 ms 257588 KB Output is correct
28 Correct 1297 ms 253676 KB Output is correct
29 Correct 1798 ms 250740 KB Output is correct
30 Correct 710 ms 224692 KB Output is correct
31 Correct 1455 ms 247336 KB Output is correct
32 Correct 458 ms 215696 KB Output is correct
33 Correct 452 ms 214168 KB Output is correct
34 Correct 615 ms 218824 KB Output is correct
35 Correct 653 ms 221404 KB Output is correct
36 Correct 471 ms 215364 KB Output is correct
37 Correct 342 ms 209400 KB Output is correct
38 Correct 301 ms 208664 KB Output is correct
39 Correct 729 ms 219580 KB Output is correct
40 Correct 414 ms 210600 KB Output is correct
41 Correct 377 ms 209916 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 188100 KB Output is correct
2 Correct 113 ms 188036 KB Output is correct
3 Correct 117 ms 188060 KB Output is correct
4 Correct 112 ms 188100 KB Output is correct
5 Correct 109 ms 188168 KB Output is correct
6 Correct 111 ms 188180 KB Output is correct
7 Correct 110 ms 188100 KB Output is correct
8 Correct 109 ms 188148 KB Output is correct
9 Correct 111 ms 188080 KB Output is correct
10 Correct 111 ms 188164 KB Output is correct
11 Correct 110 ms 188060 KB Output is correct
12 Correct 111 ms 188148 KB Output is correct
13 Correct 111 ms 188160 KB Output is correct
14 Correct 118 ms 188092 KB Output is correct
15 Correct 117 ms 188120 KB Output is correct
16 Correct 124 ms 188100 KB Output is correct
17 Correct 114 ms 188048 KB Output is correct
18 Correct 113 ms 188056 KB Output is correct
19 Correct 111 ms 188100 KB Output is correct
20 Correct 1116 ms 235408 KB Output is correct
21 Correct 1232 ms 234812 KB Output is correct
22 Correct 789 ms 224400 KB Output is correct
23 Correct 734 ms 221832 KB Output is correct
24 Correct 754 ms 224672 KB Output is correct
25 Correct 1050 ms 237712 KB Output is correct
26 Correct 921 ms 231776 KB Output is correct
27 Incorrect 1155 ms 239880 KB Output isn't correct
28 Halted 0 ms 0 KB -