oj.uz

Submission #417142

# Submission time Handle Problem Language Result Execution time Memory
417142 2021-06-03T12:08:37 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
24 / 100
 1660 ms 691012 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);

		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);
	}
}
void init_ver(std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	sweep(l, r, y);
//	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] );
	}

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188100 KB Output is correct
2 Correct 98 ms 188060 KB Output is correct
3 Correct 99 ms 188048 KB Output is correct
4 Correct 99 ms 188100 KB Output is correct
5 Correct 99 ms 188100 KB Output is correct
6 Correct 100 ms 188084 KB Output is correct
7 Correct 98 ms 188100 KB Output is correct
8 Correct 100 ms 188144 KB Output is correct
9 Correct 99 ms 188072 KB Output is correct
10 Correct 101 ms 188100 KB Output is correct
11 Correct 99 ms 188136 KB Output is correct
12 Correct 97 ms 188104 KB Output is correct
13 Correct 97 ms 188100 KB Output is correct
14 Correct 98 ms 188132 KB Output is correct
15 Correct 97 ms 188088 KB Output is correct
16 Correct 97 ms 188104 KB Output is correct
17 Correct 99 ms 188128 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 188076 KB Output is correct
2 Correct 98 ms 188124 KB Output is correct
3 Correct 1134 ms 254056 KB Output is correct
4 Correct 1159 ms 256092 KB Output is correct
5 Correct 844 ms 241084 KB Output is correct
6 Correct 803 ms 239644 KB Output is correct
7 Correct 863 ms 241248 KB Output is correct
8 Correct 1461 ms 269296 KB Output is correct
9 Correct 1022 ms 247168 KB Output is correct
10 Correct 1660 ms 284064 KB Output is correct
11 Correct 743 ms 228116 KB Output is correct
12 Correct 486 ms 218884 KB Output is correct
13 Correct 1540 ms 273844 KB Output is correct
14 Correct 501 ms 217028 KB Output is correct
15 Correct 417 ms 210624 KB Output is correct
16 Correct 383 ms 211432 KB Output is correct
17 Correct 345 ms 210172 KB Output is correct
18 Correct 669 ms 220180 KB Output is correct
19 Correct 114 ms 189512 KB Output is correct
20 Correct 211 ms 202788 KB Output is correct
21 Correct 333 ms 209352 KB Output is correct
22 Correct 302 ms 208616 KB Output is correct
23 Correct 677 ms 219904 KB Output is correct
24 Correct 367 ms 210848 KB Output is correct
25 Correct 343 ms 209844 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 194792 KB Output is correct
2 Runtime error 1129 ms 691012 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 194792 KB Output is correct
2 Runtime error 1129 ms 691012 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188100 KB Output is correct
2 Correct 98 ms 188060 KB Output is correct
3 Correct 99 ms 188048 KB Output is correct
4 Correct 99 ms 188100 KB Output is correct
5 Correct 99 ms 188100 KB Output is correct
6 Correct 100 ms 188084 KB Output is correct
7 Correct 98 ms 188100 KB Output is correct
8 Correct 100 ms 188144 KB Output is correct
9 Correct 99 ms 188072 KB Output is correct
10 Correct 101 ms 188100 KB Output is correct
11 Correct 99 ms 188136 KB Output is correct
12 Correct 97 ms 188104 KB Output is correct
13 Correct 97 ms 188100 KB Output is correct
14 Correct 98 ms 188132 KB Output is correct
15 Correct 97 ms 188088 KB Output is correct
16 Correct 97 ms 188104 KB Output is correct
17 Correct 99 ms 188128 KB Output is correct
18 Correct 98 ms 188076 KB Output is correct
19 Correct 98 ms 188124 KB Output is correct
20 Correct 1134 ms 254056 KB Output is correct
21 Correct 1159 ms 256092 KB Output is correct
22 Correct 844 ms 241084 KB Output is correct
23 Correct 803 ms 239644 KB Output is correct
24 Correct 863 ms 241248 KB Output is correct
25 Correct 1461 ms 269296 KB Output is correct
26 Correct 1022 ms 247168 KB Output is correct
27 Correct 1660 ms 284064 KB Output is correct
28 Correct 743 ms 228116 KB Output is correct
29 Correct 486 ms 218884 KB Output is correct
30 Correct 1540 ms 273844 KB Output is correct
31 Correct 501 ms 217028 KB Output is correct
32 Correct 417 ms 210624 KB Output is correct
33 Correct 383 ms 211432 KB Output is correct
34 Correct 345 ms 210172 KB Output is correct
35 Correct 669 ms 220180 KB Output is correct
36 Correct 114 ms 189512 KB Output is correct
37 Correct 211 ms 202788 KB Output is correct
38 Correct 333 ms 209352 KB Output is correct
39 Correct 302 ms 208616 KB Output is correct
40 Correct 677 ms 219904 KB Output is correct
41 Correct 367 ms 210848 KB Output is correct
42 Correct 343 ms 209844 KB Output is correct
43 Correct 181 ms 194792 KB Output is correct
44 Runtime error 1129 ms 691012 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -