Submission #1101720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101720		rainboy	Flights (JOI22_flights)	C++17	92 / 100	224 ms	2752 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 L = 20;
	const int LN = 14;	/* LN = ceil(log2(N)) */
	const int LK = 4;	/* LK = ceil(log2(K)) */
	const int LT = 7;	/* LT = ceil(log2(dp[K])) */

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

	int dp[K + 1];

	void init() {
		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;
		}
	}

	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 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_], xx[N_], hh[N_], gg[N_];
	int ii[M], iii[M][K], m;

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

	int k;

	void dfs3(int i, int h) {
		hh[i] = h, iii[h][gg[i] = k++] = i;
		for (int o = 0; o < eo[i]; o++) {
			int j = ej[i][o];
			dfs3(j, h);
		}
	}

	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]);
		int r = 0;
		while (eo[r] > 2)
			r++;
		m = 0, dfs1(-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;
			while (eo[j] >= 2)
				j = ej[j][1];
			for (int s = eo[i] < 2 ? 0 : sz[ej[i][1]]; s < B - 1; s++)
				pp[n_] = j, append(j, n_), j = n_++;
			dfs2(i);
			k = 0, dfs3(i, 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 = iii[hu][0], v = iii[hv][0], u_;
		if (hu == hv)
			return encode(LT, xx[u]);
		if (dist(u, v) != dd[v] - dd[u])
			u_ = u;
		else {
			u_ = v;
			while (hh[u_] != hh[u])
				u_ = pp[u_];
		}
		return encode(LT, xx[u]) + encode(LT, xx[v]) + encode(LK, gg[u_]) + encode(LN, dist(u_, v));
	}
}

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 L = 20;
	const int LN = 14;	/* LN = ceil(log2(N)) */
	const int LK = 4;	/* LK = ceil(log2(K)) */
	const int LT = 7;	/* LT = ceil(log2(dp[K])) */

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

	int dp[K + 1];

	void init() {
		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;
		}
	}

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

	void decode_tree(int *pp, int n, int p, int i, int x) {
		pp[i] = p;
		if (n == 1)
			return;
		int n1 = min(n - 1, B - 1), n2 = n - 1 - n1;
		while (n1 > n2 && x >= dp[n1] * dp[n2])
			x -= dp[n1] * dp[n2], n1--, n2++;
		if (n2 == 0)
			decode_tree(pp, n1, i, i + 1, x);
		else {
			int x1, x2;
			if (n1 != n2)
				x1 = x / dp[n2], x2 = x % dp[n2];
			else
				decode_pair(x, x1, x2);
			decode_tree(pp, n1, i, i + 1, x1), decode_tree(pp, n2, i, i + 1 + n1, x2);
		}
	}

	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(L, encode_pair(hu, hv));
	}

	int qu[K], ppu[K], ppv[K];

	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 answer(string cc) {
		if (hu == hv) {
			decode_tree(ppu, K, -1, 0, decode(cc));
			return dist(ppu, gu, gv);
		}
		decode_tree(ppu, K, -1, 0, decode(string(cc, 0, LT)));
		decode_tree(ppv, K, -1, 0, decode(string(cc, LT, LT)));
		int gu_ = decode(string(cc, LT * 2, LK));
		int d = decode(string(cc, LT * 2 + LK, LN));
		return dist(ppu, gu, gu_) + d + dist(ppv, 0, 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::dfs2(int)':
Ali.cpp:104:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  104 |    if (sz[j1] < sz[j2] || sz[j1] == sz[j2] && xx[j1] > xx[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: 77 / 85