제출 #1009093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009093		emptypringlescan	City (JOI17_city)	C++17	0 / 100	108 ms	78228 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];
	}
	subsz[x]=sz+1;
	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();
}
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[]){
	cnt=n;
	long double x=1.8;
	for(int i=0; i<258; 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]<<8ll|pos[i]);
	}
}

Device

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

vector<int> szs;
void InitDevice(){
	long double x=1.8;
	for(int i=0; i<258; i++){
		x*=1.05;
		szs.push_back((int)x);
	}
}
int Answer(long long a, long long b){
	long long prea=a>>8ll,posa=a^(prea<<8ll);
	long long preb=b>>8ll,posb=b^(preb<<8ll);
	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: 0 / 8
• Subtask 2: 0 / 92