| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1102252 | rainboy | Flights (JOI22_flights) | C++17 | 216 ms | 2740 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://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Ali.h"
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace Ali {
const int N = 10000, B = 7, K = B * 2, M = (N + B - 1) / B, N_ = N * 2 + K;
const int C1 = 21, C2 = 298, D = N / 2;
const int T1 = 5, T2 = 11;
const int LA = 24;
const int LB = 20;
string encode(int n, int x) {
string cc(n, '?');
for (int i = 0; i < n; i++)
cc[i] = (x >> i & 1) + '0';
return cc;
}
int decode(string cc) {
int n = cc.size(), x = 0;
for (int i = 0; i < n; i++)
if (cc[i] == '1')
x |= 1 << i;
return x;
}
int encode_pair(int i, int j) {
return j * (j + 1) / 2 + i;
}
void decode_pair(int x, int &i, int &j) {
j = 0;
while (x >= j + 1)
x -= ++j;
i = x;
}
int dist(int *pp, int i, int j) {
int d = 0;
while (i != j) {
d++;
if (i > j)
i = pp[i];
else
j = pp[j];
}
return d;
}
int ddd[C2][K], c_;
int idx(int *dd) {
for (int c = 0; c < C2; c++)
if (memcmp(ddd[c], dd, K * sizeof *dd) == 0)
return c;
memcpy(ddd[c_], dd, K * sizeof *dd);
return c_++;
}
int ppp1[T1][B] = {
{ -1, 0, 1, 1, 2, 3, 4 },
{ -1, 0, 1, 1, 2, 2, 4 },
{ -1, 0, 1, 2, 3, 3, 4 },
{ -1, 0, 0, 1, 1, 2, 3 },
{ -1, 0, 0, 1, 3, 3, 4 }
};
int gg1[T1] = { 1, 1, -1, 0, -1 };
int ppp2[T2][B - 1] = {
{ -1, 0, 1, 2, 3, 4 },
{ -1, 0, 1, 2, 3, 3 },
{ -1, 0, 1, 2, 2, 3 },
{ -1, 0, 1, 1, 2, 4 },
{ -1, 0, 1, 1, 2, 2 },
{ -1, 0, 1, 1, 2, 3 },
{ -1, 0, 0, 1, 3, 4 },
{ -1, 0, 0, 1, 3, 3 },
{ -1, 0, 0, 1, 1, 3 },
{ -1, 0, 0, 1, 2, 3 },
{ -1, 0, 0, 1, 1, 2 }
};
int group[T2] = { 2, 2, 4, 1, 1, 0, 4, 4, 3, 3, 3 }; /* on page 215 */
int pp_[K], gg_[K], tt[K], dd_[K];
void generate(int *pp, int t1, int t2, int step) {
int cnt = 0;
pp[cnt] = -1, gg_[cnt] = -1, tt[cnt] = -1, cnt++;
pp[cnt] = 0, gg_[cnt] = 0, tt[cnt] = 1, cnt++;
pp[cnt] = 0, gg_[cnt] = 0, tt[cnt] = 2, cnt++;
for (int g = 1, g1 = 1, g2 = 1; g < cnt; g++)
if (tt[g] == 1)
while (g1 < B && ppp1[t1][g1] == gg_[g])
pp[cnt] = g, gg_[cnt] = g1++, tt[cnt] = 1, cnt++;
else
while (g2 < B - 1 && ppp2[t2][g2] == gg_[g])
pp[cnt] = g, gg_[cnt] = g2++, tt[cnt] = 2, cnt++;
if (step == 1) {
for (int v = 0; v < K; v++)
dd_[v] = dist(pp, 0, v);
idx(dd_);
} else if (step == 2) {
for (int u = 0; u < K; u++) {
if (tt[u] == 1) {
if (gg_[u] == gg1[u])
continue;
} else {
int deg = 0;
for (int g2 = 1; g2 < B - 1; g2++)
if (ppp2[t2][g2] == gg_[u])
deg++;
if (deg == 2)
continue;
}
for (int v = 0; v < K; v++)
dd_[v] = dist(pp, u, v);
idx(dd_);
}
}
}
void init() {
if (c_ != 0)
return;
for (int t1 = 0; t1 < T1; t1++)
for (int t2 = 0; t2 < T2; t2++)
if (group[t2] <= t1)
generate(pp_, t1, t2, 1);
for (int t1 = 0; t1 < T1; t1++)
for (int t2 = 0; t2 < T2; t2++)
if (group[t2] <= t1)
generate(pp_, t1, t2, 2);
}
int ej[N_][3], eo[N_], dd[N_], pp[N_], sz[N_], hh[N_], gg[N_], n;
int ii[M], iii[M][K], tt1[M], tt2[M], m;
void append(int i, int j) {
ej[i][eo[i]++] = j;
}
void detach(int i, int j) {
for (int o = eo[i]; o--; )
if (ej[i][o] == j) {
ej[i][o] = ej[i][--eo[i]];
return;
}
}
void bfs(int h) {
int i = ii[h], k = 0;
hh[i] = h, iii[h][gg[i] = k++] = i;
for (int g = 0; g < k; g++) {
i = iii[h][g];
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o];
hh[j] = h, iii[h][gg[j] = k++] = j;
}
}
}
int d_, i_;
void dfs1(int p, int i, int d) {
pp[i] = p;
if (d_ < d)
d_ = d, i_ = i;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs1(i, j, d + 1);
}
}
int dfs2(int p, int i, int d) {
pp[i] = p, dd[i] = d;
detach(i, p);
int s = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
s += dfs2(i, j, d + 1);
}
sz[i] = s;
if (s >= B || p == -1) {
ii[m++] = i, s = 0;
if (p != -1)
detach(p, i);
}
return s;
}
void dfs3(int i) {
sz[i] = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs3(j);
sz[i] += sz[j];
}
if (eo[i] == 2) {
int &j1 = ej[i][0], &j2 = ej[i][1];
if (sz[j1] < sz[j2]) {
int tmp;
tmp = j1, j1 = j2, j2 = tmp;
}
}
}
int type3(int i) {
int j = ej[i][0];
return sz[j] == 2 ? 0 : 1;
}
int type4(int i) {
int j = ej[i][0];
return sz[j] == 3 ? type3(j) : 2;
}
int type5(int i) {
int j = ej[i][0];
if (sz[j] == 4)
return type4(j);
else if (sz[j] == 3)
return 3 + type3(j);
else
return 5;
}
int type(int i) {
int j = ej[i][0];
if (sz[j] == 5)
return type5(j);
else if (sz[j] == 4)
return 6 + type4(j);
else
return 9 + type3(j);
}
int qu[N];
void init(vi uu, vi vv, int n_) {
init();
n = n_;
memset(eo, 0, (n * 2 + K) * sizeof *eo);
for (int h = 0; h < n - 1; h++)
append(uu[h], vv[h]), append(vv[h], uu[h]);
d_ = -1, i_ = -1, dfs1(-1, 0, 0);
d_ = -1, dfs1(-1, i_, 0);
int cnt = 0;
while (i_ != -1)
qu[cnt++] = i_, i_ = pp[i_];
int r = -1;
for (int h1 = (cnt - 1) / 2, h2 = cnt / 2; h1 >= 0; h1--, h2++) {
if (eo[qu[h1]] <= 2) {
r = qu[h1];
break;
}
if (eo[qu[h2]] <= 2) {
r = qu[h2];
break;
}
}
m = 0, dfs2(-1, r, 0);
int tmp;
for (int h1 = 0, h2 = m - 1; h1 < h2; h1++, h2--)
tmp = ii[h1], ii[h1] = ii[h2], ii[h2] = tmp;
n_ = n;
for (int h = 0; h < m; h++) {
int i = ii[h], j;
j = i;
while (eo[j] > 0)
j = ej[j][0];
for (int s = eo[i] == 0 ? 0 : sz[ej[i][0]]; s < B - 1; s++)
dd[n_] = dd[j] + 1, pp[n_] = j, append(j, n_), j = n_++;
j = i;
if (eo[i] < 2)
j = i;
else {
j = ej[i][1];
while (eo[j] > 0)
j = ej[j][0];
}
for (int s = eo[i] < 2 ? 0 : sz[ej[i][1]]; s < B - 1; s++)
dd[n_] = dd[j] + 1, pp[n_] = j, append(j, n_), j = n_++;
int &j1 = ej[i][0], &j2 = ej[i][1];
dfs3(j1), dfs3(j2);
if (group[type(j1)] < group[type(j2)])
tmp = j1, j1 = j2, j2 = tmp;
tt1[h] = type(j1), tt2[h] = type(j2);
j = -1;
switch (tt1[h]) {
case 0:
j = ej[ej[ej[j1][0]][0]][0];
break;
case 1:
j = ej[ej[ej[ej[j1][0]][0]][0]][0];
break;
case 2:
j = j1;
break;
case 3:
j = ej[ej[j1][0]][0];
break;
case 4:
j = ej[ej[ej[j1][0]][0]][0];
break;
case 5:
j = ej[ej[ej[j1][0]][0]][0];
break;
case 6:
j = ej[ej[j1][0]][0];
break;
case 7:
j = ej[ej[ej[j1][0]][0]][0];
break;
case 8:
j = ej[j1][1];
break;
case 9:
j = ej[j1][0];
break;
case 10:
j = ej[ej[j1][0]][0];
break;
}
dd[n_] = dd[j] + 1, pp[n_] = j, append(j, n_), n_++;
tt1[h] = group[tt1[h]];
bfs(h);
}
for (int i = 0; i < n; i++)
SetID(i, hh[i] * K + gg[i]);
}
int lca(int i, int j) {
while (i != j)
if (dd[i] > dd[j])
i = pp[i];
else
j = pp[j];
return i;
}
int dist(int i, int j) {
return dd[i] + dd[j] - dd[lca(i, j)] * 2;
}
string send(string cc) {
int hu, hv; decode_pair(decode(cc), hu, hv);
int u = ii[hu], v = ii[hv], u_, x;
if (hu == hv)
x = tt1[hu] * T2 + tt2[hu];
else {
if (dist(u, v) != dd[v] - dd[u])
u_ = u;
else {
u_ = v;
while (hh[u_] != hh[u])
u_ = pp[u_];
}
int d = dist(u_, v);
for (int g = 0; g < K; g++)
dd_[g] = dist(u_, iii[hu][g]);
int cu = idx(dd_);
for (int g = 0; g < K; g++)
dd_[g] = dist(v, iii[hv][g]);
int cv = idx(dd_);
x = (d < D ? d * C2 + cu : D * C2 + (d - D) * C1 + cu) * C1 + cv;
}
x += 2;
int l = 0;
while (1 << l <= x)
l++;
return encode(l - 1, x);
}
}
void Init(int n, vi ii, vi jj) {
Ali::init(ii, jj, n);
}
string SendA(string cc) {
return Ali::send(cc);
}
/* https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Benjamin.h"
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace Benjamin {
const int N = 10000, B = 7, K = B * 2, M = (N + B - 1) / B, N_ = N * 2 + K;
const int C1 = 21, C2 = 298, D = N / 2;
const int T1 = 5, T2 = 11;
const int LA = 24;
const int LB = 20;
string encode(int n, int x) {
string cc(n, '?');
for (int i = 0; i < n; i++)
cc[i] = (x >> i & 1) + '0';
return cc;
}
int decode(string cc) {
int n = cc.size(), x = 0;
for (int i = 0; i < n; i++)
if (cc[i] == '1')
x |= 1 << i;
return x;
}
int encode_pair(int i, int j) {
return j * (j + 1) / 2 + i;
}
void decode_pair(int x, int &i, int &j) {
j = 0;
while (x >= j + 1)
x -= ++j;
i = x;
}
int dist(int *pp, int i, int j) {
int d = 0;
while (i != j) {
d++;
if (i > j)
i = pp[i];
else
j = pp[j];
}
return d;
}
int ddd[C2][K], c_;
int idx(int *dd) {
for (int c = 0; c < C2; c++)
if (memcmp(ddd[c], dd, K * sizeof *dd) == 0)
return c;
memcpy(ddd[c_], dd, K * sizeof *dd);
return c_++;
}
int ppp1[T1][B] = {
{ -1, 0, 1, 1, 2, 3, 4 },
{ -1, 0, 1, 1, 2, 2, 4 },
{ -1, 0, 1, 2, 3, 3, 4 },
{ -1, 0, 0, 1, 1, 2, 3 },
{ -1, 0, 0, 1, 3, 3, 4 }
};
int gg1[T1] = { 1, 1, -1, 0, -1 };
int ppp2[T2][B - 1] = {
{ -1, 0, 1, 2, 3, 4 },
{ -1, 0, 1, 2, 3, 3 },
{ -1, 0, 1, 2, 2, 3 },
{ -1, 0, 1, 1, 2, 4 },
{ -1, 0, 1, 1, 2, 2 },
{ -1, 0, 1, 1, 2, 3 },
{ -1, 0, 0, 1, 3, 4 },
{ -1, 0, 0, 1, 3, 3 },
{ -1, 0, 0, 1, 1, 3 },
{ -1, 0, 0, 1, 2, 3 },
{ -1, 0, 0, 1, 1, 2 }
};
int group[T2] = { 2, 2, 4, 1, 1, 0, 4, 4, 3, 3, 3 }; /* on page 215 */
int pp_[K], gg_[K], tt[K], dd_[K];
void generate(int *pp, int t1, int t2, int step) {
int cnt = 0;
pp[cnt] = -1, gg_[cnt] = -1, tt[cnt] = -1, cnt++;
pp[cnt] = 0, gg_[cnt] = 0, tt[cnt] = 1, cnt++;
pp[cnt] = 0, gg_[cnt] = 0, tt[cnt] = 2, cnt++;
for (int g = 1, g1 = 1, g2 = 1; g < cnt; g++)
if (tt[g] == 1)
while (g1 < B && ppp1[t1][g1] == gg_[g])
pp[cnt] = g, gg_[cnt] = g1++, tt[cnt] = 1, cnt++;
else
while (g2 < B - 1 && ppp2[t2][g2] == gg_[g])
pp[cnt] = g, gg_[cnt] = g2++, tt[cnt] = 2, cnt++;
if (step == 1) {
for (int v = 0; v < K; v++)
dd_[v] = dist(pp, 0, v);
idx(dd_);
} else if (step == 2) {
for (int u = 0; u < K; u++) {
if (tt[u] == 1) {
if (gg_[u] == gg1[u])
continue;
} else {
int deg = 0;
for (int g2 = 1; g2 < B - 1; g2++)
if (ppp2[t2][g2] == gg_[u])
deg++;
if (deg == 2)
continue;
}
for (int v = 0; v < K; v++)
dd_[v] = dist(pp, u, v);
idx(dd_);
}
}
}
void init() {
if (c_ != 0)
return;
for (int t1 = 0; t1 < T1; t1++)
for (int t2 = 0; t2 < T2; t2++)
if (group[t2] <= t1)
generate(pp_, t1, t2, 1);
for (int t1 = 0; t1 < T1; t1++)
for (int t2 = 0; t2 < T2; t2++)
if (group[t2] <= t1)
generate(pp_, t1, t2, 2);
}
int n, hu, gu, hv, gv;
string send(int n_, int u, int v) {
init();
n = n_;
if (u > v) {
int tmp;
tmp = u, u = v, v = tmp;
}
hu = u / K, gu = u % K, hv = v / K, gv = v % K;
return encode(LB, encode_pair(hu, hv));
}
int answer(string cc) {
int x = decode(cc + "1") - 2;
if (hu == hv) {
int t1 = x / T2, t2 = x % T2;
generate(pp_, t1, t2, 0);
return dist(pp_, gu, gv);
}
int d, cu, cv;
cv = x % C1, x /= C1;
if (x < D * C2)
cu = x % C2, d = x / C2;
else {
x -= D * C2;
cu = x % C1, d = D + x / C1;
}
return ddd[cu][gu] + d + ddd[cv][gv];
}
}
string SendB(int n, int u, int v) {
return Benjamin::send(n, u, v);
}
int Answer(string cc) {
return Benjamin::answer(cc);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||