Submission #489159

#	Time	Username	Problem	Language	Result	Execution time	Memory
489159		flappybird	City (JOI17_city)	C++14	100 / 100	450 ms	47100 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 400
namespace {
	ll opof[MAX]; //onepointofive
	vector<ll> adj[303030];
	ll ord[303030];
	ll num[303030];
	ll tnum[303030];
	ll cnt = 0;
}
ll dfs(ll x, ll p = -1) {
	num[x] = 1;
	ord[x] = ++cnt;
	ll sum = 0;
	for (auto v : adj[x]) {
		if (v == p) continue;
		ll res = dfs(v, x);
		num[x] += res;
		sum += res;
		cnt = ord[x] + sum;
	}
	tnum[x] = lower_bound(opof, opof + MAX, num[x]) - opof;
	num[x] = opof[tnum[x]];
	return num[x];
}
void Encode(int N, int A[], int B[]) {
	ll i;
	for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);
	for (i = 0; i < N - 1; i++) adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
	dfs(0);
	for (i = 0; i < N; i++) {
		Code(i, ord[i] * (MAX) + tnum[i]);
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 400

ll opof[MAX];

void InitDevice() {
	ll i;
	for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);	
}

int Answer(long long S, long long T) {
	ll sl, sr, tl, tr;
	sl = S / MAX;
	tl = T / MAX;
	sr = sl + opof[S % MAX];
	tr = tl + opof[T % MAX];
	if (sl <= tl && tr <= sr) return 1;
	else if (tl <= sl && sr <= tr) return 0;
	else return 2;
}

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