Submission #1102182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102182		rainboy	Flights (JOI22_flights)	C++17	98 / 100	215 ms	2312 KiB

Ali

/* https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Ali.h"
#include <cstring>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace Ali {
	const int N = 10000, B = 7, K = B * 2 - 1, M = (N + B - 1) / B, N_ = N + K;
	const int C = 548, C_ = 38, D = N / 2 + 1;
	const int T = 66;	/* T = dp[K] */
	const int LA = 26;	/* LA = ceil((D * C + (N - D) * C_) * C_) - 1 */
	const int LB = 20;
	const int LN = 14;	/* LN = ceil(log2(N)) */
	const int LK = 4;	/* LK = ceil(log2(K)) */
	const int LT = 7;	/* LT = ceil(log2(T)) */

	int min(int a, int b) { return a < b ? a : b; }

	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 dp[K + 1];

	int dd_[K], pp_[K], sz_[K], tt_[K];

	void decode_tree(int *pp, int t) {
		int n_ = 1;
		pp[0] = -1, sz_[0] = K, tt_[0] = t;
		for (int i = 0; i < n_; i++) {
			int n = sz_[i], t = tt_[i];
			if (n == 1)
				continue;
			int n1 = min(n - 1, B - 1), n2 = n - 1 - n1;
			while (n1 > n2 && t >= dp[n1] * dp[n2])
				t -= dp[n1] * dp[n2], n1--, n2++;
			if (n2 == 0)
				pp[n_] = i, sz_[n_] = n1, tt_[n_] = t, n_++;
			else {
				int t1, t2;
				if (n1 != n2)
					t1 = t / dp[n2], t2 = t % dp[n2];
				else
					decode_pair(t, t1, t2);
				pp[n_] = i, sz_[n_] = n1, tt_[n_] = t1, n_++;
				pp[n_] = i, sz_[n_] = n2, tt_[n_] = t2, n_++;
			}
		}
	}

	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[C][K], cnt;

	int idx(int *dd) {
		for (int c = 0; c < C; c++)
			if (memcmp(ddd[c], dd, K * sizeof *dd) == 0)
				return c;
		memcpy(ddd[cnt], dd, K * sizeof *dd);
		return cnt++;
	}

	void init() {
		if (cnt != 0)
			return;
		memset(dp, 0, (K + 1) * sizeof *dp), dp[0] = 1;
		for (int s1 = 0; s1 < B; s1++) {
			for (int s2 = 0; s2 < s1; s2++)
				dp[s1 + s2 + 1] += dp[s1] * dp[s2];
			dp[s1 + s1 + 1] += dp[s1] * (dp[s1] + 1) / 2;
		}
		for (int t = 0; t < T; t++) {
			decode_tree(pp_, t);
			for (int i = 0; i < K; i++)
				dd_[i] = dist(pp_, 0, i);
			idx(dd_);
		}
		for (int t = 0; t < T; t++) {
			decode_tree(pp_, t);
			for (int i = 1, j = 0; i < K; i++) {
				while (j < K && pp_[j] < i)
					j++;
				if (j + 1 < K && pp_[j + 1] == i)
					continue;
				for (int j_ = 0; j_ < K; j_++)
					dd_[j_] = dist(pp_, i, j_);
				idx(dd_);
			}
		}
	}

	int ej[N_][3], eo[N_], n;

	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;
			}
	}

	int dd[N_], pp[N_], sz[N_], tt[N_], hh[N_], gg[N_];
	int ii[M], iii[M][K], m;

	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] == 0)
			tt[i] = 0;
		else if (eo[i] == 1)
			tt[i] = tt[ej[i][0]];
		else {
			int &j1 = ej[i][0], &j2 = ej[i][1];
			if (sz[j1] < sz[j2] || sz[j1] == sz[j2] && tt[j1] > tt[j2]) {
				int tmp;
				tmp = j1, j1 = j2, j2 = tmp;
			}
			tt[i] = 0;
			for (int n1 = min(sz[i] - 1, B - 1), n2 = sz[i] - 1 - n1; n1 > sz[j1]; n1--, n2++)
				tt[i] += dp[n1] * dp[n2];
			tt[i] += sz[j1] != sz[j2] ? tt[j1] * dp[sz[j2]] + tt[j2] : encode_pair(tt[j1], tt[j2]);
		}
	}

	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 qu[N];

	void init(vi uu, vi vv, int n_) {
		init();
		n = n_;
		memset(eo, 0, (n + 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;
		for (int h = m - 1; h >= 0; h--) {
			int i = ii[h], j, n_ = n;
			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++)
				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++)
				pp[n_] = j, append(j, n_), j = n_++;
			dfs3(i);
			bfs(h);
			while (n_-- > n)
				detach(pp[n_], n_);
		}
		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 = tt[u];
		else {
			if (dist(u, v) != dd[v] - dd[u])
				u_ = u;
			else {
				u_ = v;
				while (hh[u_] != hh[u])
					u_ = pp[u_];
			}
			decode_tree(pp_, tt[u]);
			for (int g = 0; g < K; g++)
				dd_[g] = dist(pp_, gg[u_], g);
			int cu = idx(dd_);
			decode_tree(pp_, tt[v]);
			for (int g = 0; g < K; g++)
				dd_[g] = dist(pp_, gg[v], g);
			int d = dist(u_, v);
			int cv = idx(dd_);
			x = (d < D ? d * C + cu : D * C + (d - D) * C_ + cu) * C_ + 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);
}

Benjamin

/* 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 - 1, M = (N + B - 1) / B, N_ = N + K;
	const int C = 548, C_ = 38, D = N / 2 + 1;
	const int T = 66;	/* T = dp[K] */
	const int LA = 26;	/* LA = ceil((D * C + (N - D) * C_) * C_) - 1 */
	const int LB = 20;
	const int LN = 14;	/* LN = ceil(log2(N)) */
	const int LK = 4;	/* LK = ceil(log2(K)) */
	const int LT = 7;	/* LT = ceil(log2(T)) */

	int min(int a, int b) { return a < b ? a : b; }

	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 dp[K + 1];

	int dd_[K], pp_[K], sz_[K], tt_[K];

	void decode_tree(int *pp, int t) {
		int n_ = 1;
		pp[0] = -1, sz_[0] = K, tt_[0] = t;
		for (int i = 0; i < n_; i++) {
			int n = sz_[i], t = tt_[i];
			if (n == 1)
				continue;
			int n1 = min(n - 1, B - 1), n2 = n - 1 - n1;
			while (n1 > n2 && t >= dp[n1] * dp[n2])
				t -= dp[n1] * dp[n2], n1--, n2++;
			if (n2 == 0)
				pp[n_] = i, sz_[n_] = n1, tt_[n_] = t, n_++;
			else {
				int t1, t2;
				if (n1 != n2)
					t1 = t / dp[n2], t2 = t % dp[n2];
				else
					decode_pair(t, t1, t2);
				pp[n_] = i, sz_[n_] = n1, tt_[n_] = t1, n_++;
				pp[n_] = i, sz_[n_] = n2, tt_[n_] = t2, n_++;
			}
		}
	}

	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[C][K], cnt;

	int idx(int *dd) {
		for (int c = 0; c < C; c++)
			if (memcmp(ddd[c], dd, K * sizeof *dd) == 0)
				return c;
		memcpy(ddd[cnt], dd, K * sizeof *dd);
		return cnt++;
	}

	void init() {
		if (cnt != 0)
			return;
		memset(dp, 0, (K + 1) * sizeof *dp), dp[0] = 1;
		for (int s1 = 0; s1 < B; s1++) {
			for (int s2 = 0; s2 < s1; s2++)
				dp[s1 + s2 + 1] += dp[s1] * dp[s2];
			dp[s1 + s1 + 1] += dp[s1] * (dp[s1] + 1) / 2;
		}
		for (int t = 0; t < T; t++) {
			decode_tree(pp_, t);
			for (int i = 0; i < K; i++)
				dd_[i] = dist(pp_, 0, i);
			idx(dd_);
		}
		for (int t = 0; t < T; t++) {
			decode_tree(pp_, t);
			for (int i = 1, j = 0; i < K; i++) {
				while (j < K && pp_[j] < i)
					j++;
				if (j + 1 < K && pp_[j + 1] == i)
					continue;
				for (int j_ = 0; j_ < K; j_++)
					dd_[j_] = dist(pp_, i, j_);
				idx(dd_);
			}
		}
	}

	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) {
			decode_tree(pp_, x);
			return dist(pp_, gu, gv);
		}
		int d, cu, cv;
		cv = x % C_, x /= C_;
		if (x < D * C)
			cu = x % C, d = x / C;
		else {
			x -= D * C;
			cu = x % C_, d = D + x / C_;
		}
		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)

Ali.cpp: In function 'void Ali::dfs3(int)':
Ali.cpp:188:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  188 |    if (sz[j1] < sz[j2] || sz[j1] == sz[j2] && tt[j1] > tt[j2]) {
      |                           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 83 / 85