Submission #21023

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21023	2017-03-29T16:04:39 Z	model_code	City (JOI17_city)	C++11	100 / 100	598 ms	57936 KB

Encoder

#include "Encoder.h"

#include <vector>
using namespace std;

const int kMaxN = 250000;
const int kMaxDepth = 18;
const double kRatio = 1.05;

static vector<int> graph[kMaxN];
static vector<int> widths;

static int lf[kMaxN], rg[kMaxN], last_id;

void SetWidths()
{
	int w = 1;
	widths.push_back((int)w);
	int times = kMaxDepth + 1;
	while (times > 0) {
		int w2 = w * kRatio;
		if (w == w2) ++w2;
		widths.push_back(w2);
		if (w2 > kMaxN) {
			--times;
		}
		w = w2;
	}
}

int ceiling(int w)
{
	return *(lower_bound(widths.begin(), widths.end(), w));
}

void visit(int p, int rt)
{
	lf[p] = last_id++;
	for (int q : graph[p]) if (q != rt) {
		visit(q, p);
	}
	rg[p] = last_id = lf[p] + ceiling(last_id - lf[p]);
}

void Encode(int N, int A[], int B[])
{
	SetWidths();
	for (int i = 0; i < N - 1; ++i) {
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	last_id = 0;
	visit(0, -1);
	for (int i = 0; i < N; ++i) {
		int wc = lower_bound(widths.begin(), widths.end(), rg[i] - lf[i]) - widths.begin();
		long long code = (long long)lf[i] * widths.size() + wc;
		Code(i, code);
	}
}

Device

#include "Device.h"

#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

const int kMaxN = 250000;
const int kMaxDepth = 18;
const double kRatio = 1.05;

static vector<int> widths;

void InitDevice()
{
	int w = 1;
	widths.push_back((int)w);
	int times = kMaxDepth + 1;
	while (times > 0) {
		int w2 = w * kRatio;
		if (w == w2) ++w2;
		widths.push_back(w2);
		if (w2 > kMaxN) {
			--times;
		}
		w = w2;
	}
}

pair<int, int> range(long long code)
{
	int left = (int)(code / widths.size());
	int w = widths[(int)(code % widths.size())];
	return{ left, left + w };
}

int Answer(long long S, long long T)
{
	pair<int, int> X = range(S), Y = range(T);
	if (Y.first <= X.first && X.second <= Y.second) return 0;
	if (X.first <= Y.first && Y.second <= X.second) return 1;
	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12488 KB	Output is correct
2	Correct	8 ms	12288 KB	Output is correct
3	Correct	8 ms	12528 KB	Output is correct
4	Correct	8 ms	12288 KB	Output is correct
5	Correct	9 ms	12288 KB	Output is correct
6	Correct	8 ms	12288 KB	Output is correct
7	Correct	8 ms	12544 KB	Output is correct
8	Correct	9 ms	12288 KB	Output is correct
9	Correct	9 ms	12288 KB	Output is correct
10	Correct	9 ms	12288 KB	Output is correct
11	Correct	9 ms	12544 KB	Output is correct
12	Correct	11 ms	12288 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	20208 KB	Output is correct - L = 181278
2	Correct	173 ms	20200 KB	Output is correct - L = 190512
3	Correct	174 ms	20472 KB	Output is correct - L = 175446
4	Correct	173 ms	20376 KB	Output is correct - L = 176175
5	Correct	516 ms	57272 KB	Output is correct - L = 72767565
6	Correct	511 ms	56824 KB	Output is correct - L = 73679301
7	Correct	507 ms	56688 KB	Output is correct - L = 74319849
8	Correct	503 ms	55792 KB	Output is correct - L = 80807220
9	Correct	448 ms	57816 KB	Output is correct - L = 120973176
10	Correct	433 ms	56928 KB	Output is correct - L = 119730474
11	Correct	439 ms	57936 KB	Output is correct - L = 138558600
12	Correct	440 ms	56760 KB	Output is correct - L = 125678385
13	Correct	598 ms	55888 KB	Output is correct - L = 96938532
14	Correct	517 ms	55736 KB	Output is correct - L = 79096986
15	Correct	168 ms	19440 KB	Output is correct - L = 178848
16	Correct	168 ms	19440 KB	Output is correct - L = 181521
17	Correct	170 ms	19424 KB	Output is correct - L = 174717
18	Correct	479 ms	55632 KB	Output is correct - L = 131961150
19	Correct	487 ms	55656 KB	Output is correct - L = 60749757
20	Correct	493 ms	55648 KB	Output is correct - L = 60749757
21	Correct	495 ms	55720 KB	Output is correct - L = 125678142
22	Correct	511 ms	55592 KB	Output is correct - L = 61189344
23	Correct	504 ms	55560 KB	Output is correct - L = 61353369
24	Correct	562 ms	55416 KB	Output is correct - L = 62296209
25	Correct	529 ms	55416 KB	Output is correct - L = 62570313
26	Correct	545 ms	55120 KB	Output is correct - L = 63344511
27	Correct	549 ms	55176 KB	Output is correct - L = 63552519