Submission #118379

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118379	2019-06-18T20:32:55 Z	Mamnoon_Siam	City (JOI17_city)	C++17	100 / 100	545 ms	66536 KB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

const double R = 1.054;
const int maxn = 2.5e5 + 5;

int tym = 0;
vector<int> lg, g[maxn];
int length(int x) {
	return *lower_bound(lg.begin(), lg.end(), x); }
int Log(int x) {
	return lower_bound(lg.begin(), lg.end(), x) - lg.begin(); }

void dfs(int u, int p) {
	int L = tym++;
	for(int v : g[u]) if(v != p) {
		dfs(v, u);
	}
	tym = L + length(tym - L);
	Code(u, L << 8 | Log(tym - L));
}

void Encode(int N, int A[], int B[]) {
	{
		lg.clear();
		double p = 1;
		while(p < 1000000000.0) {
			lg.emplace_back(floor(p));
			p *= R;
		}
		sort(lg.begin(), lg.end());
		lg.erase(unique(lg.begin(), lg.end()), lg.end());
	}
	for(int i = 0; i < N - 1; i++) {
		int u = A[i], v = B[i];
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	} dfs(0, -1);
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

#define lg antilog

const double R = 1.054;
const int maxn = 2.5e5 + 5;

vector<int> lg;

void InitDevice() {
	double p = 1;
	while(p < 1000000000.0) {
		lg.emplace_back(floor(p));
		p *= R;
	}
	sort(lg.begin(), lg.end());
	lg.erase(unique(lg.begin(), lg.end()), lg.end());
}

pair<int, int> decode(long long code) {
	return {code >> 8, (code >> 8) + lg[code & ((1 << 8) - 1)] - 1};
}

int Answer(long long u, long long v) {
	int ul, ur, vl, vr;
	tie(ul, ur) = decode(u);
	tie(vl, vr) = decode(v);
	if(vl <= ul and ur <= vr) return 0;
	if(ul <= vl and vr <= ur) return 1;
	return 2;
}

Subtask #1

8.0 / 8.0

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

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	26360 KB	Output is correct - L = 187136
2	Correct	169 ms	26656 KB	Output is correct - L = 199424
3	Correct	168 ms	26608 KB	Output is correct - L = 192512
4	Correct	169 ms	26352 KB	Output is correct - L = 196608
5	Correct	500 ms	64752 KB	Output is correct - L = 80686848
6	Correct	529 ms	65032 KB	Output is correct - L = 79586304
7	Correct	538 ms	64752 KB	Output is correct - L = 77641728
8	Correct	513 ms	64496 KB	Output is correct - L = 100383232
9	Correct	465 ms	66520 KB	Output is correct - L = 139817728
10	Correct	453 ms	66520 KB	Output is correct - L = 138472704
11	Correct	460 ms	66536 KB	Output is correct - L = 153785344
12	Correct	448 ms	66520 KB	Output is correct - L = 138432768
13	Correct	487 ms	66248 KB	Output is correct - L = 104320256
14	Correct	500 ms	65136 KB	Output is correct - L = 82966784
15	Correct	172 ms	26608 KB	Output is correct - L = 192256
16	Correct	172 ms	26296 KB	Output is correct - L = 198144
17	Correct	201 ms	26608 KB	Output is correct - L = 184064
18	Correct	487 ms	65168 KB	Output is correct - L = 145906944
19	Correct	545 ms	65304 KB	Output is correct - L = 63999744
20	Correct	535 ms	65264 KB	Output is correct - L = 63999744
21	Correct	512 ms	65248 KB	Output is correct - L = 138432512
22	Correct	507 ms	65248 KB	Output is correct - L = 65110272
23	Correct	499 ms	64736 KB	Output is correct - L = 65283072
24	Correct	520 ms	65008 KB	Output is correct - L = 65562880
25	Correct	521 ms	64976 KB	Output is correct - L = 66335232
26	Correct	544 ms	65008 KB	Output is correct - L = 67560192
27	Correct	520 ms	65016 KB	Output is correct - L = 68271360