Submission #1224708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224708		mychecksedad	City (JOI17_city)	C++20	100 / 100	294 ms	30512 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const ll N = 250000, M = 1e5+10, K = 52, MX = 30;
const double rt = 1.05;
int ww = 19;

vector<ll> W;
ll timer = 0, tin[N], tout[N];
vi g[N];

void dfs(int v, int p){
	tin[v] = timer++;
	for(int u: g[v]){
		if(u != p) dfs(u, v);
	}
	tout[v] = timer = tin[v] + (*lower_bound(all(W), timer - tin[v]));
}

void initW(){
	ll w = 1;
	W.pb(w);
	while(ww){
		ll nw = floor((double)w * rt);
		if(nw == w) ++nw;
		if(nw > N) --ww;
		W.pb(nw);
		w = nw;
	}
}

void code(int i, ll x){
	Code(i, x);
}

void Encode(int n, int A[], int B[])
{
	initW();
	for(int i = 0; i + 1 < n; ++i){
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	dfs(0, 0);
	ll ws = W.size();
	for(int i = 0; i < n; ++i){
		code(i, tin[i] * ws + (lower_bound(all(W), (tout[i] - tin[i])) - W.begin()));
	}
}

Device

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const ll N = 250000, M = 1e5+10, K = 52, MX = 30;
const double rtt = 1.05;
int www = 19;

vector<ll> WW;
ll wss;

void initWW(){
	ll w = 1;
	WW.pb(w);
	while(www){
		ll nw = floor((double)w * rtt);
		if(nw == w) ++nw;
		if(nw > N) --www;
		WW.pb(nw);
		w = nw;
	}
}

void InitDevice()
{
	initWW();
	wss = WW.size();
}

bool is_ancestor(array<ll, 2> u, array<ll, 2> v){
	return u[0] <= v[0] && v[1] <= u[1];
}


int Answer(long long S, long long T)
{
	array<ll, 2> u = {S / wss, S / wss + WW[S % wss]}; 
	array<ll, 2> v = {T / wss, T / wss + WW[T % wss]}; 
	if(is_ancestor(u, v)) return 1;
	if(is_ancestor(v, u)) return 0;
	return 2;
}

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