제출 #1031083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031083		s_tree	City (JOI17_city)	C++17	18 / 100	240 ms	55564 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 250'010;
vector<long long> nums;
vector<int> g[N];
int tim=0;

long long f[N], s[N];

void dfs(int at, int p) {
	f[at] = tim;
	for(int to:g[at]) {
		if(to==p)continue;
		dfs(to, at);
	}
	s[at]=tim++;
//	auto it = lower_bound(nums.begin(), nums.end(), tim-f[at]);
//	s[at] = it-nums.begin();
//	tim += (*it);
}


void Encode(int n, int A[], int B[])
{
	long double d = 1.05;
	long double val = d;
	while(val <= 3*N) {
		if(!nums.size() or nums.back()!=(int)val)
			nums.push_back(val);
		val*=d;
	}
	for(int i=0;i+1<n;i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	dfs(0, -1);
	for(int i = 0;i<n;i++) {
//		cout << f[i] << " " << f[i]+nums[s[i]]-1 << "\n";
//		cout << ((long long)s[i]*N*3 +f[i])/3*N << endl;
		Code(i, (long long)(f[i])*N*3ll + s[i]);
	}
//	cout << "A" << endl;	
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
const long long N = 250'010;
vector<long long> nms;
void InitDevice()
{
	long double d = 1.05;
	long double val = d;
	while(val <= 3*N) {
		if(!nms.size() or nms.back()!=(int)val)
			nms.push_back(val);
		val*=d;
	}
}

int Answer(long long S, long long T)
{
//	cout << nms.size() << " " << (S/(3*N)) << endl;
//	cout << nms.size() << " " << (T/(3*N)) << endl;
	long long fs = S/(3*N);
	long long ss = S%(3*N);
	long long ft = T/(3*N);
	long long st = T%(3*N);
//	cout << fs << " " << ss << endl;
//	cout << ft << " " << st << endl;
//	cout << endl;
	if(fs <= ft and st <= ss)return 1;
	if(ft <= fs and ss <= st)return 0;
	return 2;
}

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