Submission #250935

#	Time	Username	Problem	Language	Result	Execution time	Memory
250935		imeimi2000	City (JOI17_city)	C++17	100 / 100	584 ms	70616 KiB

Encoder

#include "Encoder.h"
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
typedef long long llong;
 
static const int MAXN = 2.5e5;
static const double mul = 1.021;
static vector<int> ls;
 
static void pushElement() {
    int x = ls.back();
    int y = x * mul;
    if (x == y) ++y;
    ls.push_back(y);
}
 
static void init() {
    ls.clear();
    ls.push_back(1);
    while (ls.back() <= MAXN) pushElement();
    for (int i = 0; i < 20; ++i) pushElement();
}
 
static int n;
static vector<int> edge[MAXN];
static int st[MAXN];
static int sz[MAXN];
static int ord;
 
static int lowbound(int x) {
    return lower_bound(ls.begin(), ls.end(), x) - ls.begin();
}
 
static void dfs(int x, int p) {
    st[x] = ord++;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs(i, x);
    }
    int l = lowbound(ord - st[x]);
    ord = st[x] + ls[sz[x] = l];
}
 
void Encode(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n; ++i) edge[i].clear();
	init();
	for (int i = 0; i < n - 1; ++i) {
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
	}
	ord = 0;
	dfs(0, -1);
	for (int i = 0; i < n; ++i) {
        Code(i, st[i] * ls.size() + sz[i]);
	}
}

Device

#include "Device.h"
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
typedef long long llong;
 
static const int MAXN = 2.5e5;
static const double mul = 1.021;
static vector<int> ls;
 
static void pushElement() {
    int x = ls.back();
    int y = x * mul;
    if (x == y) ++y;
    ls.push_back(y);
}
 
static void init() {
    ls.clear();
    ls.push_back(1);
    while (ls.back() <= MAXN) pushElement();
    for (int i = 0; i < 20; ++i) pushElement();
}
 
void InitDevice() {
    init();
}
 
int Answer(llong S, llong T) {
    int st1 = S / ls.size();
    int st2 = T / ls.size();
    int ed1 = st1 + ls[S % ls.size()] - 1;
    int ed2 = st2 + ls[T % ls.size()] - 1;
    if (st1 <= st2 && ed2 <= ed1) return 1;
    if (st2 <= st1 && ed1 <= ed2) return 0;
	return 2;
}

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