oj.uz

답안 #417106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417106 2021-06-03T11:48:13 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 692584 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];
}

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]);
		}
	}
	xup[s].pb(0), xup[g].pb(0);


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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 188100 KB Output is correct
2 Correct 106 ms 188060 KB Output is correct
3 Correct 105 ms 188044 KB Output is correct
4 Correct 106 ms 188060 KB Output is correct
5 Correct 106 ms 188192 KB Output is correct
6 Correct 105 ms 188112 KB Output is correct
7 Correct 104 ms 188096 KB Output is correct
8 Correct 106 ms 188076 KB Output is correct
9 Correct 107 ms 188180 KB Output is correct
10 Correct 106 ms 188120 KB Output is correct
11 Correct 103 ms 188116 KB Output is correct
12 Correct 104 ms 188156 KB Output is correct
13 Correct 105 ms 188128 KB Output is correct
14 Correct 105 ms 188100 KB Output is correct
15 Correct 107 ms 188120 KB Output is correct
16 Correct 105 ms 188100 KB Output is correct
17 Correct 105 ms 188096 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 188072 KB Output is correct
2 Correct 105 ms 188052 KB Output is correct
3 Correct 1294 ms 253988 KB Output is correct
4 Correct 1217 ms 260352 KB Output is correct
5 Correct 895 ms 244840 KB Output is correct
6 Correct 1404 ms 243180 KB Output is correct
7 Correct 867 ms 244896 KB Output is correct
8 Correct 1649 ms 271260 KB Output is correct
9 Correct 1063 ms 247492 KB Output is correct
10 Correct 1792 ms 284204 KB Output is correct
11 Correct 806 ms 228320 KB Output is correct
12 Correct 510 ms 218668 KB Output is correct
13 Correct 1481 ms 274324 KB Output is correct
14 Correct 3396 ms 217052 KB Output is correct
15 Correct 1891 ms 210700 KB Output is correct
16 Correct 438 ms 211564 KB Output is correct
17 Correct 413 ms 210124 KB Output is correct
18 Execution timed out 4075 ms 197080 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 194708 KB Output is correct
2 Runtime error 1169 ms 692584 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 194708 KB Output is correct
2 Runtime error 1169 ms 692584 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 188100 KB Output is correct
2 Correct 106 ms 188060 KB Output is correct
3 Correct 105 ms 188044 KB Output is correct
4 Correct 106 ms 188060 KB Output is correct
5 Correct 106 ms 188192 KB Output is correct
6 Correct 105 ms 188112 KB Output is correct
7 Correct 104 ms 188096 KB Output is correct
8 Correct 106 ms 188076 KB Output is correct
9 Correct 107 ms 188180 KB Output is correct
10 Correct 106 ms 188120 KB Output is correct
11 Correct 103 ms 188116 KB Output is correct
12 Correct 104 ms 188156 KB Output is correct
13 Correct 105 ms 188128 KB Output is correct
14 Correct 105 ms 188100 KB Output is correct
15 Correct 107 ms 188120 KB Output is correct
16 Correct 105 ms 188100 KB Output is correct
17 Correct 105 ms 188096 KB Output is correct
18 Correct 106 ms 188072 KB Output is correct
19 Correct 105 ms 188052 KB Output is correct
20 Correct 1294 ms 253988 KB Output is correct
21 Correct 1217 ms 260352 KB Output is correct
22 Correct 895 ms 244840 KB Output is correct
23 Correct 1404 ms 243180 KB Output is correct
24 Correct 867 ms 244896 KB Output is correct
25 Correct 1649 ms 271260 KB Output is correct
26 Correct 1063 ms 247492 KB Output is correct
27 Correct 1792 ms 284204 KB Output is correct
28 Correct 806 ms 228320 KB Output is correct
29 Correct 510 ms 218668 KB Output is correct
30 Correct 1481 ms 274324 KB Output is correct
31 Correct 3396 ms 217052 KB Output is correct
32 Correct 1891 ms 210700 KB Output is correct
33 Correct 438 ms 211564 KB Output is correct
34 Correct 413 ms 210124 KB Output is correct
35 Execution timed out 4075 ms 197080 KB Time limit exceeded
36 Halted 0 ms 0 KB -