Submission #117098

#	Time	Username	Problem	Language	Result	Execution time	Memory
117098		Mamnoon_Siam	City (JOI17_city)	C++17	30 / 100	573 ms	67296 KiB

Encoder

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

const int maxn = 1 << 18;
const int half = 125001, full = 250000;
vector<int> g[maxn];
int tym = 0;
pair<int, int> optimize(int L, int R) {
	int diff = R - L;
	if(250000 - diff < diff) {
		diff = 250000 - diff;
		L = R;
	} return {L, diff};
}
void dfs(int u, int p) {
	int L = tym++, R, l, diff;
	for(int v : g[u]) if(v - p) {
		dfs(v, u);
	} R = tym - 1;
	tie(l, diff) = optimize(L, R);
	Code(u, 1LL * l * 125001 + diff);
}
void Encode(int N, int A[], int B[]) {
	for(int i = 0; i < N - 1; i++) {
		int u = A[i], v = B[i];
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	} dfs(0, -1);
}

Device

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

const int half = 125001, full = 250000;
 
void InitDevice() {}

pair<int, int> fix(int L, int diff) {
	int R = L + diff;
	if(R >= full) {
		R -= full;
		swap(R, L);
	} return {L, R};
}
 
int Answer(long long u, long long v) {
	int ul, ur, vl, vr;
	tie(ul, ur) = fix(u / half, u % half);
	tie(vl, vr) = fix(v / half, v % half);
	if(vl <= ul and ur <= vr) return 0;
	if(ul <= vl and vr <= ur) return 1;
	return 2;
}

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