oj.uz

Submission #89158

# Submission time Handle Problem Language Result Execution time Memory
89158 2018-12-10T16:07:21 Z nikolapesic2802 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 442 ms 177480 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

static const int MAXN = 100000;
static const int DEPTH = 20;

using namespace std;

struct segtree
{
	static const int kDepth = 17;
	static const int kSize = 1 << kDepth;
	pair<int, int> *data;

	segtree() {
		data = new pair<int, int>[2 * kSize];
	}
	void init(int len, int* v)
	{
		for (int i = 0; i < len; ++i) data[kSize + i] = make_pair(v[i], -i);
		for (int i = len; i < kSize; ++i) data[kSize + i] = make_pair(-1, -i);
		for (int i = kSize - 1; i >= 1; --i) data[i] = max(data[i * 2], data[i * 2 + 1]);
	}
	pair<int, int> query(int l, int r)
	{
		l += kSize;
		r += kSize;
		pair<int, int> ret(-1, -1);
		while (l < r) {
			if (l & 1) ret = max(ret, data[l++]);
			if (r & 1) ret = max(ret, data[--r]);
			l >>= 1; r >>= 1;
		}
		ret.second = -ret.second;
		return ret;
	}
};

int N, K, Q;
int L[MAXN];
vector<int> child[MAXN * 2]; int dep[MAXN * 2], ci[MAXN * 2];
int nlast, root;
int wnode[MAXN];
segtree lst;
bool nonstop;

int parent[MAXN * 6][DEPTH], weight[MAXN * 6][DEPTH];

int build(int l, int r)
{
	if (r - l == 1) {
		return wnode[l] = nlast++;
	}
	auto tmp = lst.query(l + 1, r);
	int bp = tmp.first;
	vector<int> sep;
	sep.push_back(l);
	sep.push_back(tmp.second);
	for (;;) {
		auto q = lst.query(sep.back() + 1, r);
		if (q.first != bp) break;
		sep.push_back(q.second);
	}
	sep.push_back(r);

	int ret = nlast++;
	for (int i = 0; i < (int)sep.size() - 1; ++i) {
		child[ret].push_back(build(sep[i], sep[i + 1]));
	}
	return ret;
}
inline int forest_vtx(int p, int mode)
{
	// mode 0: (x+1, x), 1: (x, x), 2: (x, x+1)
	return p * 3 + mode;
}
void assign_parent(int p, int par, int tl, int tr)
{
	tl = min(tl, tr + 1);
	tr = min(tr, tl + 1);
	if (tl == tr + 1) {
		parent[p][0] = forest_vtx(par, 0);
		weight[p][0] = tr;
	} else if (tl == tr) {
		parent[p][0] = forest_vtx(par, 1);
		weight[p][0] = tr;
	} else {
		parent[p][0] = forest_vtx(par, 2);
		weight[p][0] = tl;
	}
}
void gen_forest(int p)
{
	for (int p2 = p * 3; p2 < (p + 1) * 3; ++p2) {
		for (int i = 1; i < DEPTH; ++i) {
			if (parent[p2][i - 1] == -1) {
				parent[p2][i] = -1;
				weight[p2][i] = weight[p2][i - 1];
			} else {
				parent[p2][i] = parent[parent[p2][i - 1]][i - 1];
				weight[p2][i] = weight[p2][i - 1] + weight[parent[p2][i - 1]][i - 1];
			}
		}
	}
	for (int i = 0; i < child[p].size(); ++i) {
		int q = child[p][i];
		int j = (int)child[p].size() - i - 1;
		dep[q] = dep[p] + 1;
		ci[q] = i;
		assign_parent(forest_vtx(q, 0), p, 1 + i, j);
		assign_parent(forest_vtx(q, 1), p, i, j);
		assign_parent(forest_vtx(q, 2), p, i, j + 1);
		gen_forest(q);
	}
}
pair<int, int> descend(int p, int d)
{
	int dist = 0;
	for (int i = DEPTH - 1; i >= 0; --i) if (d & (1 << i)) {
		dist += weight[p][i];
		p = parent[p][i];
	}
	return{ p, dist };
}
int solve(int a, int b)
{
	if (b == a + 1) return 1;
	int p = forest_vtx(wnode[a], 2);
	int q = forest_vtx(wnode[b - 1], 0);
	int dist = 0;
	if (dep[p / 3] < dep[q / 3]) {
		auto tmp = descend(q, dep[q / 3] - dep[p / 3]);
		dist = tmp.second;
		q = tmp.first;
	} else if (dep[p / 3] > dep[q / 3]) {
		auto tmp = descend(p, dep[p / 3] - dep[q / 3]);
		dist = tmp.second;
		p = tmp.first;
	}
	for (int i = DEPTH - 1; i >= 0; --i) {
		if (parent[p][i] / 3 != parent[q][i] / 3) {
			dist += weight[p][i] + weight[q][i];
			p = parent[p][i];
			q = parent[q][i];
		}
	}
	int ret = N;
	ret = min(ret, dist + ci[q / 3] - ci[p / 3] - 1 + (p % 3 == 2 ? 1 : 0) + (q % 3 == 0 ? 1 : 0));
	if (parent[p][0] / 3 != root || nonstop) {
		ret = min(ret, dist + ci[p / 3] + ((int)child[parent[p][0] / 3].size() - ci[q / 3] - 1) + (p % 3 == 0 ? 1 : 0) + (q % 3 == 2 ? 1 : 0) + 1);
	}
	return ret;
}
int main()
{
	scanf("%d%d%d", &N, &K, &Q);
	nonstop = true;
	for (int i = 0; i < N; ++i) {
		scanf("%d", L + i);
		--L[i];
		if (i != 0 && i != N - 1 && L[i] == K - 1) nonstop = false;
	}
	
	nlast = 0;
	lst.init(N, L);
	root = build(0, N - 1);
	dep[root] = 0; ci[root] = 0;
	for (int i = 0; i < 3; ++i) {
		parent[root * 3 + i][0] = -1;
		weight[root * 3 + i][0] = 0;
	}
	gen_forest(root);

	for (int q = 0; q < Q; ++q) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a; --b;
		if (a > b) swap(a, b);
		printf("%d\n", solve(a, b) - 1);
	}
	return 0;
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &K, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", L + i);
   ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 8 ms 7392 KB Output is correct
3 Correct 8 ms 7500 KB Output is correct
4 Correct 7 ms 7612 KB Output is correct
5 Correct 8 ms 7612 KB Output is correct
6 Correct 8 ms 7612 KB Output is correct
7 Correct 9 ms 7612 KB Output is correct
8 Correct 8 ms 7620 KB Output is correct
9 Correct 8 ms 7624 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8524 KB Output is correct
2 Correct 142 ms 92284 KB Output is correct
3 Correct 165 ms 98356 KB Output is correct
4 Correct 170 ms 103232 KB Output is correct
5 Correct 162 ms 105320 KB Output is correct
6 Correct 176 ms 108008 KB Output is correct
7 Correct 182 ms 109064 KB Output is correct
8 Correct 90 ms 109064 KB Output is correct
9 Correct 164 ms 109064 KB Output is correct
10 Correct 129 ms 109064 KB Output is correct
11 Correct 165 ms 109064 KB Output is correct
12 Correct 172 ms 109064 KB Output is correct
13 Correct 157 ms 109064 KB Output is correct
14 Correct 164 ms 109064 KB Output is correct
15 Correct 165 ms 109064 KB Output is correct
16 Correct 164 ms 109064 KB Output is correct
17 Correct 151 ms 114212 KB Output is correct
18 Correct 151 ms 114768 KB Output is correct
19 Correct 161 ms 115604 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 115604 KB Output is correct
2 Correct 289 ms 115604 KB Output is correct
3 Correct 297 ms 115604 KB Output is correct
4 Correct 315 ms 115604 KB Output is correct
5 Correct 300 ms 115604 KB Output is correct
6 Correct 293 ms 115604 KB Output is correct
7 Correct 316 ms 116452 KB Output is correct
8 Correct 224 ms 116452 KB Output is correct
9 Correct 160 ms 116452 KB Output is correct
10 Correct 186 ms 116452 KB Output is correct
11 Correct 196 ms 116452 KB Output is correct
12 Correct 181 ms 116452 KB Output is correct
13 Correct 181 ms 116452 KB Output is correct
14 Correct 204 ms 116452 KB Output is correct
15 Correct 196 ms 116452 KB Output is correct
16 Correct 248 ms 116452 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 139488 KB Output is correct
2 Correct 324 ms 141172 KB Output is correct
3 Correct 303 ms 142888 KB Output is correct
4 Correct 270 ms 144552 KB Output is correct
5 Correct 143 ms 144552 KB Output is correct
6 Correct 282 ms 144552 KB Output is correct
7 Correct 327 ms 144552 KB Output is correct
8 Correct 244 ms 144552 KB Output is correct
9 Correct 279 ms 144552 KB Output is correct
10 Correct 271 ms 144552 KB Output is correct
11 Correct 261 ms 144552 KB Output is correct
12 Correct 274 ms 144552 KB Output is correct
13 Correct 278 ms 144552 KB Output is correct
14 Correct 375 ms 151780 KB Output is correct
15 Correct 391 ms 160792 KB Output is correct
16 Correct 442 ms 174276 KB Output is correct
17 Correct 419 ms 174276 KB Output is correct
18 Correct 392 ms 174276 KB Output is correct
19 Correct 417 ms 174276 KB Output is correct
20 Correct 346 ms 174276 KB Output is correct
21 Correct 312 ms 174276 KB Output is correct
22 Correct 316 ms 175484 KB Output is correct
23 Correct 305 ms 177480 KB Output is correct