Submission #1009416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009416		siewjh	City (JOI17_city)	C++17	100 / 100	259 ms	51644 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
	const ll MAXN = 250005;
	vector<int> adj[MAXN];
	ll pwr[300], ind = -1;
}
void dfs(int x, int par){
	ll st = ++ind;
	for (int nn : adj[x]){
		if (nn == par) continue;
		dfs(nn, x);
	}
	ll sz = ind - st + 1;
	int lg = lower_bound(pwr, pwr + 300, sz) - pwr;
	ind += pwr[lg] - sz;
	Code(x, st * 300 + lg);
}
void Encode(int N, int A[], int B[]){
	pwr[0] = 1;
	for (int i = 1; i < 300; i++) pwr[i] = ceil(pwr[i - 1] * 1.05);
	for (int i = 0; i < N - 1; ++i) {
		int a = A[i], b = B[i];
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(0, -1);
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
	ll pwr[300];
}
void InitDevice(){
	pwr[0] = 1;
	for (int i = 1; i < 300; i++) pwr[i] = ceil(pwr[i - 1] * 1.05);
}
int Answer(ll S, ll T){
	ll sta = S / 300, ena = sta + pwr[S % 300] - 1, stb = T / 300, enb = stb + pwr[T % 300] - 1;
	if (sta >= stb && ena <= enb) return 0;
	else if (stb >= sta && enb <= ena) return 1;
	return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92