제출 #1009111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009111		emptypringlescan	City (JOI17_city)	C++17	99 / 100	265 ms	106236 KiB

Encoder

#include <bits/stdc++.h>
using namespace std;
#include "Encoder.h"
vector<int> adj[2500005];
long long pre[2500005],pos[2500005];
vector<int> szs;
int cur=0,cnt;
int subsz[2500005];
void fsz(int x, int p){
	int sz=0;
	for(int i:adj[x]){
		if(i==p) continue;
		fsz(i,x);
		sz+=subsz[i];
	}
	int lol=*lower_bound(szs.begin(),szs.end(),sz);
	for(int i=sz+1; i<=lol; i++) adj[x].push_back(cnt),cnt++;
	pos[x]=lower_bound(szs.begin(),szs.end(),sz)-szs.begin();
  subsz[x]=szs[pos[x]]+1;
}
void dfs(int x, int p){
	cur++;
	pre[x]=cur;
	for(int i:adj[x]){
		if(i!=p) dfs(i,x);
	}
}
void Encode(int n, int u[], int v[]){
  szs.push_back(0);
	cnt=n;
	long double x=1.8;
	for(int i=0; i<400; i++){
		x*=1.05;
		szs.push_back((int)x);
	}
	for(int i=0; i<n-1; i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	fsz(0,-1);
	dfs(0,-1);
	for(int i=0; i<n; i++){
		Code(i,pre[i]<<9ll|pos[i]);
	}
}

Device

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

vector<int> szs;
void InitDevice(){
	long double x=1.8;
  szs.push_back(0);
	for(int i=0; i<400; i++){
		x*=1.05;
		szs.push_back((int)x);
	}
}
int Answer(long long a, long long b){
	long long prea=a>>9ll,posa=a^(prea<<9ll);
	long long preb=b>>9ll,posb=b^(preb<<9ll);
	posa=szs[posa]+prea;
	posb=szs[posb]+preb;
	if(preb<=prea&&posa<=posb) return 0;
	else if(prea<=preb&&posb<=posa) return 1;
	return 2;
}

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