Submission #427862

#	Time	Username	Problem	Language	Result	Execution time	Memory
427862		jamezzz	City (JOI17_city)	C++17	100 / 100	581 ms	53712 KiB

Encoder

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

#define maxn 250005
int pre[maxn],pst[maxn],cnt;
vector<int> seq,AL[maxn];

void build(){
	const long double factor = 1.055645;
	seq.pb(0);seq.pb(1);
	for(int i=2;i<256;++i){
		int x=(int)(factor*seq.back());
		if(x==seq.back())++x;
		seq.pb(x);
	}
}

void dfs(int u){
	pre[u]=cnt++;
	for(int v:AL[u]){
		if(pre[v]==-1)dfs(v);
	}
	int pos=lower_bound(all(seq),cnt-pre[u])-seq.begin();
	cnt+=seq[pos]+pre[u]-cnt;
	pst[u]=cnt-1;
}

void Encode(int n,int a[],int b[]){
	build();
	memset(pre,-1,sizeof pre);
	for(int i=0;i<n-1;++i){
		AL[a[i]].pb(b[i]);
		AL[b[i]].pb(a[i]);
	}
	dfs(0);
	//for(int i=0;i<n;++i)pf("%d %d\n",pre[i],pst[i]);
	for(int i=0;i<n;++i){
		int dist=pst[i]-pre[i]+1;
		int x=lower_bound(all(seq),dist)-seq.begin();
		assert(x<sz(seq)&&seq[x]==dist);
		Code(i,(1ll<<20)*x+pre[i]);
	}
}

Device

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

int ones=(1<<20)-1;

vector<int> seq2;

void build2(){
	const long double factor = 1.055645;
	seq2.pb(0);seq2.pb(1);
	for(int i=2;i<256;++i){
		int x=(int)(factor*seq2.back());
		if(x==seq2.back())++x;
		seq2.pb(x);
	}
}

void InitDevice(){
	build2();
}

int Answer(ll S, ll T){
	ll preS=S&ones,preT=T&ones;
	ll distS=S>>20,distT=T>>20;
	ll pstS=preS+seq2[distS]-1,pstT=preT+seq2[distT]-1;
	//pf("S: %lld %lld %lld\n",preS,distS,pstS);
	//pf("T: %lld %lld %lld\n",preT,distT,pstT);
	if(preT<=preS&&preS<=pstT)return 0;
	if(preS<=preT&&preT<=pstS)return 1;
	return 2;
}

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