Submission #300540

#	Time	Username	Problem	Language	Result	Execution time	Memory
300540		mode149256	City (JOI17_city)	C++14	100 / 100	625 ms	70872 KiB

Encoder

/*input

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

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 250101;

vi lens1;
int n;
vii edges(MX);
int piv = 0;
vi st(MX);
vi ilgis(MX);

void genLens1() {
	double R = 1.05;

	int cur = 1;

	while (cur < 180 * MX) {
		lens1.emplace_back(cur);

		cur = max(cur + 1, (int)round(R * cur));
	}
}

void dfs(int x, int p) {
	st[x] = piv++;

	for (auto u : edges[x]) {
		if (u != p)
			dfs(u, x);
	}

	int ind = lower_bound(lens1.begin(), lens1.end(), piv - st[x]) - lens1.begin();

	piv = st[x] + lens1[ind];
	ilgis[x] = ind;
}

void Encode(int N, int A[], int B[])
{
	n = N;
	genLens1();
	for (int i = 0; i < N - 1; ++i)
	{
		edges[A[i]].emplace_back(B[i]);
		edges[B[i]].emplace_back(A[i]);
	}

	dfs(0, -1);
	for (int i = 0; i < N; ++i) {
		// printf("i = %d, code = %lld, st = %d, ilgis = %d\n", i, (ll)st[i]*lens1.size() + ilgis[i], st[i], lens1[ilgis[i]]);
		Code(i, (ll)st[i]*lens1.size() + ilgis[i]);
	}
}

Device

/*input

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

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 250101;

vi lens2;

void genLens2() {
	double R = 1.05;

	int cur = 1;

	while (cur < 180 * MX) {
		lens2.emplace_back(cur);

		cur = max(cur + 1, (int)round(R * cur));
	}
}

void InitDevice()
{
	genLens2();
}

int Answer(ll S, ll T)
{
	int sx = S / lens2.size();
	int sy = T / lens2.size();
	int xlen = lens2[S % lens2.size()];
	int ylen = lens2[T % lens2.size()];

	// printf("S = %d, st = %d, ilgis = %d\n", S, sx, xlen);
	// printf("T = %d, st = %d, ilgis = %d\n", S, sy, ylen);

	if (sx <= sy and sy + ylen <= sx + xlen) return 1;
	else if (sy <= sx and sx + xlen <= sy + ylen) return 0;
	else return 2;
}

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