Submission #434263

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
434263	2021-06-20 20:25:25	jhwest2	City (JOI17_city)	C++14	100 / 100	565 ms	51904 KiB

Encoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Device

 
 
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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