| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 685246 | rainboy | City (JOI17_city) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d4-city-review.pdf */
#include "Encoder.h"
#include <stdlib.h>
static const int N = 250000, N_ = 601654, H = 18;
static const double B = 1.05;
static int len[N + 1], m;
static void InitEncoder() {
m = 0;
len[0] = 1;
while (len[m] <= N_)
len[m + 1] = (int) ((len[m] + 1) * B), m++;
}
static int lg(int n) {
int lower = -1, upper = m;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (len[h] >= n)
upper = h;
else
lower = h;
}
return upper;
}
static int *ej[N], eo[N], hh[N];
static void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
static void dfs1(int p, int i, int x) {
int s = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j, x + s);
s += len[hh[j]];
}
}
hh[i] = lg(s);
Code(i, hh[i] * N_ + x);
}
void Encode(int n, int *ii, int *jj) {
InitEncoder();
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int h = 0; h < n - 1; h++)
append(ii[h], jj[h]), append(jj[h], ii[h]);
dfs1(-1, 0, 0);
}
/* https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d4-city-review.pdf */
#include "Device.h"
static const int N = 250000, N_ = 601654, H = 18;
static const double B = 1.05;
static int len[N + 1];
void InitDevice() {
int m = 0;
len[0] = 1;
while (len[m] <= N_)
len[m + 1] = (int) ((len[m] + 1) * B), m++;
}
int Answer(long long x, long long y) {
int ta1 = x % N_, tb1 = ta1 + len[x / N_];
int ta2 = y % N_, tb2 = ta2 + len[y / N_];
if (ta2 <= ta1 && tb1 <= tb2)
return 0;
if (ta1 <= ta2 && tb2 <= tb1)
return 1;
return 2;
}