oj.uz

Submission #21010

# Submission time Handle Problem Language Result Execution time Memory
21010 2017-03-29T09:35:16 Z model_code Railway Trip (JOI17_railway_trip) C++11
100 / 100
 353 ms 117216 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:29: 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:21: 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:24: 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 0 ms 104008 KB Output is correct
2 Correct 3 ms 104008 KB Output is correct
3 Correct 3 ms 104008 KB Output is correct
4 Correct 0 ms 104008 KB Output is correct
5 Correct 0 ms 104008 KB Output is correct
6 Correct 0 ms 104008 KB Output is correct
7 Correct 0 ms 104008 KB Output is correct
8 Correct 0 ms 104008 KB Output is correct
9 Correct 3 ms 104008 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 104008 KB Output is correct
2 Correct 79 ms 106316 KB Output is correct
3 Correct 89 ms 106656 KB Output is correct
4 Correct 86 ms 106912 KB Output is correct
5 Correct 83 ms 107044 KB Output is correct
6 Correct 76 ms 107176 KB Output is correct
7 Correct 89 ms 107176 KB Output is correct
8 Correct 39 ms 105628 KB Output is correct
9 Correct 106 ms 110300 KB Output is correct
10 Correct 69 ms 108364 KB Output is correct
11 Correct 89 ms 107508 KB Output is correct
12 Correct 86 ms 107520 KB Output is correct
13 Correct 113 ms 107532 KB Output is correct
14 Correct 93 ms 107528 KB Output is correct
15 Correct 89 ms 107532 KB Output is correct
16 Correct 103 ms 107524 KB Output is correct
17 Correct 93 ms 107176 KB Output is correct
18 Correct 93 ms 107176 KB Output is correct
19 Correct 93 ms 107204 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 106524 KB Output is correct
2 Correct 206 ms 106392 KB Output is correct
3 Correct 193 ms 106524 KB Output is correct
4 Correct 216 ms 106524 KB Output is correct
5 Correct 209 ms 106656 KB Output is correct
6 Correct 229 ms 106656 KB Output is correct
7 Correct 229 ms 106656 KB Output is correct
8 Correct 143 ms 105336 KB Output is correct
9 Correct 159 ms 105628 KB Output is correct
10 Correct 139 ms 105628 KB Output is correct
11 Correct 119 ms 105632 KB Output is correct
12 Correct 136 ms 105628 KB Output is correct
13 Correct 123 ms 105628 KB Output is correct
14 Correct 129 ms 104812 KB Output is correct
15 Correct 149 ms 104700 KB Output is correct
16 Correct 149 ms 105064 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 107176 KB Output is correct
2 Correct 216 ms 107176 KB Output is correct
3 Correct 206 ms 107176 KB Output is correct
4 Correct 196 ms 107176 KB Output is correct
5 Correct 126 ms 105628 KB Output is correct
6 Correct 289 ms 110296 KB Output is correct
7 Correct 266 ms 110292 KB Output is correct
8 Correct 226 ms 108356 KB Output is correct
9 Correct 263 ms 107528 KB Output is correct
10 Correct 233 ms 107524 KB Output is correct
11 Correct 256 ms 107508 KB Output is correct
12 Correct 279 ms 107520 KB Output is correct
13 Correct 246 ms 107516 KB Output is correct
14 Correct 319 ms 112104 KB Output is correct
15 Correct 339 ms 113948 KB Output is correct
16 Correct 353 ms 117216 KB Output is correct
17 Correct 296 ms 108792 KB Output is correct
18 Correct 269 ms 109264 KB Output is correct
19 Correct 266 ms 109272 KB Output is correct
20 Correct 223 ms 106092 KB Output is correct
21 Correct 243 ms 107176 KB Output is correct
22 Correct 213 ms 107176 KB Output is correct
23 Correct 223 ms 107200 KB Output is correct