oj.uz

Submission #417140

# Submission time Handle Problem Language Result Execution time Memory
417140 2021-06-03T12:06:47 Z Kevin_Zhang_TW Sky Walking (IOI19_walk) C++17
10 / 100
 1401 ms 254444 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 = 3;

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);
		DE(i);
		debug(AI(ally));

		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:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
walk.cpp:51:3: note: in expansion of macro 'DE'
   51 |   DE(i);
      |   ^~
walk.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
walk.cpp:52:3: note: in expansion of macro 'debug'
   52 |   debug(AI(ally));
      |   ^~~~~
walk.cpp: In function 'void init_ver(std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   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:121:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   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:147:3: note: in expansion of macro 'DE'
  147 |   DE(x, d);
      |   ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 188140 KB Output is correct
2 Correct 113 ms 188124 KB Output is correct
3 Correct 125 ms 188056 KB Output is correct
4 Correct 110 ms 188080 KB Output is correct
5 Correct 110 ms 188132 KB Output is correct
6 Correct 108 ms 188156 KB Output is correct
7 Correct 115 ms 188156 KB Output is correct
8 Correct 113 ms 188100 KB Output is correct
9 Correct 120 ms 188068 KB Output is correct
10 Correct 120 ms 188128 KB Output is correct
11 Correct 111 ms 188192 KB Output is correct
12 Correct 111 ms 188164 KB Output is correct
13 Correct 110 ms 188052 KB Output is correct
14 Correct 108 ms 188108 KB Output is correct
15 Correct 106 ms 188060 KB Output is correct
16 Correct 110 ms 188076 KB Output is correct
17 Correct 104 ms 188064 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 188124 KB Output is correct
2 Correct 111 ms 188028 KB Output is correct
3 Correct 755 ms 218960 KB Output is correct
4 Incorrect 1401 ms 254444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 194688 KB Output is correct
2 Incorrect 721 ms 215344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 194688 KB Output is correct
2 Incorrect 721 ms 215344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 188140 KB Output is correct
2 Correct 113 ms 188124 KB Output is correct
3 Correct 125 ms 188056 KB Output is correct
4 Correct 110 ms 188080 KB Output is correct
5 Correct 110 ms 188132 KB Output is correct
6 Correct 108 ms 188156 KB Output is correct
7 Correct 115 ms 188156 KB Output is correct
8 Correct 113 ms 188100 KB Output is correct
9 Correct 120 ms 188068 KB Output is correct
10 Correct 120 ms 188128 KB Output is correct
11 Correct 111 ms 188192 KB Output is correct
12 Correct 111 ms 188164 KB Output is correct
13 Correct 110 ms 188052 KB Output is correct
14 Correct 108 ms 188108 KB Output is correct
15 Correct 106 ms 188060 KB Output is correct
16 Correct 110 ms 188076 KB Output is correct
17 Correct 104 ms 188064 KB Output is correct
18 Correct 108 ms 188124 KB Output is correct
19 Correct 111 ms 188028 KB Output is correct
20 Correct 755 ms 218960 KB Output is correct
21 Incorrect 1401 ms 254444 KB Output isn't correct
22 Halted 0 ms 0 KB -