답안 #60376 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60376	2018-07-24T03:33:18 Z	admin	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	598 ms	177052 KB

railway_trip

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	7416 KB	Output is correct
2	Correct	12 ms	7492 KB	Output is correct
3	Correct	11 ms	7552 KB	Output is correct
4	Correct	12 ms	7608 KB	Output is correct
5	Correct	11 ms	7608 KB	Output is correct
6	Correct	6 ms	7608 KB	Output is correct
7	Correct	12 ms	7608 KB	Output is correct
8	Correct	13 ms	7640 KB	Output is correct
9	Correct	12 ms	7640 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	8516 KB	Output is correct
2	Correct	168 ms	92272 KB	Output is correct
3	Correct	176 ms	98480 KB	Output is correct
4	Correct	197 ms	103156 KB	Output is correct
5	Correct	209 ms	105384 KB	Output is correct
6	Correct	227 ms	108172 KB	Output is correct
7	Correct	242 ms	109080 KB	Output is correct
8	Correct	80 ms	109080 KB	Output is correct
9	Correct	216 ms	109080 KB	Output is correct
10	Correct	139 ms	109080 KB	Output is correct
11	Correct	197 ms	109080 KB	Output is correct
12	Correct	195 ms	109080 KB	Output is correct
13	Correct	199 ms	109080 KB	Output is correct
14	Correct	191 ms	109080 KB	Output is correct
15	Correct	200 ms	109080 KB	Output is correct
16	Correct	215 ms	109080 KB	Output is correct
17	Correct	195 ms	114296 KB	Output is correct
18	Correct	205 ms	114896 KB	Output is correct
19	Correct	207 ms	115596 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	365 ms	115596 KB	Output is correct
2	Correct	347 ms	115596 KB	Output is correct
3	Correct	325 ms	115596 KB	Output is correct
4	Correct	289 ms	115596 KB	Output is correct
5	Correct	342 ms	115596 KB	Output is correct
6	Correct	305 ms	115596 KB	Output is correct
7	Correct	388 ms	116548 KB	Output is correct
8	Correct	240 ms	116548 KB	Output is correct
9	Correct	184 ms	116548 KB	Output is correct
10	Correct	220 ms	116548 KB	Output is correct
11	Correct	193 ms	116548 KB	Output is correct
12	Correct	186 ms	116548 KB	Output is correct
13	Correct	206 ms	116548 KB	Output is correct
14	Correct	278 ms	116548 KB	Output is correct
15	Correct	264 ms	116548 KB	Output is correct
16	Correct	266 ms	116548 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	316 ms	139436 KB	Output is correct
2	Correct	325 ms	141328 KB	Output is correct
3	Correct	378 ms	142788 KB	Output is correct
4	Correct	351 ms	144736 KB	Output is correct
5	Correct	182 ms	144736 KB	Output is correct
6	Correct	454 ms	144736 KB	Output is correct
7	Correct	501 ms	144736 KB	Output is correct
8	Correct	348 ms	144736 KB	Output is correct
9	Correct	370 ms	144736 KB	Output is correct
10	Correct	355 ms	144736 KB	Output is correct
11	Correct	457 ms	144736 KB	Output is correct
12	Correct	447 ms	144736 KB	Output is correct
13	Correct	418 ms	144736 KB	Output is correct
14	Correct	558 ms	151512 KB	Output is correct
15	Correct	468 ms	160564 KB	Output is correct
16	Correct	598 ms	174132 KB	Output is correct
17	Correct	451 ms	174132 KB	Output is correct
18	Correct	415 ms	174132 KB	Output is correct
19	Correct	431 ms	174132 KB	Output is correct
20	Correct	373 ms	174132 KB	Output is correct
21	Correct	349 ms	174132 KB	Output is correct
22	Correct	429 ms	175248 KB	Output is correct
23	Correct	414 ms	177052 KB	Output is correct

답안 #60376

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 25.0 / 25.0

Subtask #4 55.0 / 55.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
25.0 / 25.0

Subtask #4
55.0 / 55.0