| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 685246 |
2023-01-23T18:01:45 Z |
rainboy |
City (JOI17_city) |
C |
|
0 ms |
0 KB |
/* 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;
}
Compilation message
Encoder.c:8:12: error: variably modified 'len' at file scope
8 | static int len[N + 1], m;
| ^~~
Encoder.c:29:13: error: variably modified 'ej' at file scope
29 | static int *ej[N], eo[N], hh[N];
| ^~
Encoder.c:29:20: error: variably modified 'eo' at file scope
29 | static int *ej[N], eo[N], hh[N];
| ^~
Encoder.c:29:27: error: variably modified 'hh' at file scope
29 | static int *ej[N], eo[N], hh[N];
| ^~
Encoder.c: In function 'append':
Encoder.c:33:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
33 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
At top level:
Encoder.c:5:43: warning: 'H' defined but not used [-Wunused-const-variable=]
5 | static const int N = 250000, N_ = 601654, H = 18;
| ^
Device.c:7:12: error: variably modified 'len' at file scope
7 | static int len[N + 1];
| ^~~
Device.c:4:43: warning: 'H' defined but not used [-Wunused-const-variable=]
4 | static const int N = 250000, N_ = 601654, H = 18;
| ^
