Submission #434263

#	Time	Username	Problem	Language	Result	Execution time	Memory
434263		jhwest2	City (JOI17_city)	C++14	100 / 100	565 ms	51904 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 1 << 18, N = 1 << 8;

static int n, in, A[M], B[M], K[N];
vector<int> G[M];

void dfs(int p, int cur) {
	lint l = ++in, r;
	for (int x : G[cur]) if (p != x) {
		dfs(cur, x);
	}
	int x = lower_bound(K, K + N, in + 1 - l) - K;
	in = l + K[x] - 1;
	Code(cur, (l << 8) + x);
}
void Encode(int _n, int A[], int B[]) {
	n = _n;
	for (int i = 0; i + 1 < n; i++) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	K[0] = 1;
	for (int i = 1; i < N; i++) {
		K[i] = max(K[i - 1] + 1, K[i - 1] * 21 / 20);
	}
	dfs(0, 0);
}

Device

#include "Device.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int N = 1 << 8;

static int K[N];
void InitDevice()
{
	K[0] = 1;
	for (int i = 1; i < N; i++) {
		K[i] = max(K[i - 1] + 1, K[i - 1] * 21 / 20);
	}
}

int Answer(lint s, lint t)
{
	lint ls = s >> 8, rs = ls + K[s & N - 1] - 1;
	lint lt = t >> 8, rt = lt + K[t & N - 1] - 1;
	if (lt <= ls && ls <= rt) return 0;
	if (ls <= lt && lt <= rs) return 1;
	return 2;
}

Compilation message (stderr)

Encoder.cpp: In function 'void dfs(int, int)':
Encoder.cpp:14:17: warning: unused variable 'r' [-Wunused-variable]
   14 |  lint l = ++in, r;
      |                 ^
Encoder.cpp: At global scope:
Encoder.cpp:10:25: warning: 'B' defined but not used [-Wunused-variable]
   10 | static int n, in, A[M], B[M], K[N];
      |                         ^
Encoder.cpp:10:19: warning: 'A' defined but not used [-Wunused-variable]
   10 | static int n, in, A[M], B[M], K[N];
      |                   ^

Device.cpp: In function 'int Answer(lint, lint)':
Device.cpp:21:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  lint ls = s >> 8, rs = ls + K[s & N - 1] - 1;
      |                                    ~~^~~
Device.cpp:22:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  lint lt = t >> 8, rt = lt + K[t & N - 1] - 1;
      |                                    ~~^~~

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