Submission #1008991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008991		PenguinsAreCute	City (JOI17_city)	C++17	100 / 100	242 ms	41828 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define sth cout<<"line "<<__LINE__<<"\n"
namespace {
	const ld r = 1.053;
	vector<ll> v;
	ll pre[250005], sub[250005], cnt;
	vector<int> adj[250005];
	void dfs(int x, int p) {
		pre[x]=cnt++;
		sub[x]=1;
		for(auto i: adj[x]) if(i!=p) {dfs(i,x); sub[x] += sub[i];}
		sub[x] = *lower_bound(v.begin(),v.end(),sub[x]);
		cnt = pre[x] + sub[x];
	}
}
void Encode(int N, int A[], int B[])
{
	ld x = 1;
	for(int i=0;i<267;i++) {
		if(!v.size()||floor(x)!=v.back()) v.push_back(floor(x));
		x *= r;
	}
	for(int i=0;i<N-1;i++) adj[A[i]].push_back(B[i]),adj[B[i]].push_back(A[i]);
	dfs(0,-1);
	for (int i = 0; i < N; ++i) {
		Code(i, 267*pre[i]+lower_bound(v.begin(),v.end(),sub[i])-v.begin());
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define sth cout<<"line "<<__LINE__<<"\n"
namespace {
	const ld r = 1.053;
	vector<ll> v;
}
void InitDevice() {
	ld x = 1;
	for(int i=0;i<267;i++) {
		if(!v.size()||floor(x)!=v.back()) v.push_back(floor(x));
		x *= r;
	}
}
int Answer(long long S, long long T) {
	int sp = S / 267, ss = v[S % 267], tp = T / 267, ts = v[T % 267];
	if(sp>=tp&&sp+ss<=tp+ts) return 0;
	if(tp>=sp&&tp+ts<=sp+ss) return 1;
	return 2;
}

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