Submission #118379

#	Time	Username	Problem	Language	Result	Execution time	Memory
118379		Mamnoon_Siam	City (JOI17_city)	C++17	100 / 100	545 ms	66536 KiB

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 / 8
• Subtask 2: 92 / 92