Submission #1170222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170222		Tob	City (JOI17_city)	C++20	100 / 100	254 ms	30564 KiB

Encoder

#include <bits/stdc++.h>
#include "Encoder.h"

#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int maxn = 25e4 + 7;

int tim;
vector <int> adj[maxn];
ll st[maxn], siz[maxn];
vector <ll> v;

void dfs(int x, int p = -1) {
	st[x] = tim++;
	siz[x] = 1;
	for (int y : adj[x]) if (y != p) {
		dfs(y, x);
		siz[x] += siz[y];
	}
	int pp = lower_bound(all(v), siz[x]) - v.begin();
	siz[x] = v[pp];
	tim = st[x] + siz[x];
	Code(x, (st[x] << 8) + pp);
}

void Encode(int n, int a[], int b[]) {
	v = {1};
	for (int i = 0; i <= 400; i++) v.pb((v[i]*21+19)/20);
	for (int i = 0; i < n-1; i++) adj[a[i]].pb(b[i]), adj[b[i]].pb(a[i]);
	dfs(0);
}

Device

#include <bits/stdc++.h>
#include "Device.h"

#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

vector <ll> v;

void InitDevice() {
	v = {1};
	for (int i = 0; i < 255; i++) v.pb((v[i]*21+19)/20);
}

int Answer(ll S, ll T) {
	int o = 1;
	ll sta = (S >> 8), stb = (T >> 8);
	if (sta > stb) swap(S, T), swap(sta, stb), o = 0;
	ll siza = (S & (1 << 8)-1);
	if (sta+v[siza] <= stb) return 2;
	return o;
}

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