Submission #1101226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101226		rainboy	Flights (JOI22_flights)	C++17	59 / 100	143 ms	2480 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;
	const int L = 20;
	const int LN = 14;	/* LN = ceil(log2(N)) */
	const int LK = 4;	/* LK = ceil(log2(K)) */

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

	void encode(string &aa, int i_, int n, int x) {
		for (int i = 0; i < n; i++)
			aa[i_ + i] = (x >> i & 1) + '0';
	}

	int decode(string &aa, int i_, int n) {
		int x = 0;
		for (int i = 0; i < n; i++)
			if (aa[i_ + i] == '1')
				x |= 1 << i;
		return x;
	}

	void decode_pair(int n, int x, int &i, int &j) {
		i = 0;
		while (x >= n - i)
			x -= n - i++;
		j = i + x;
	}

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

	void append(int i, int j) {
		ej[i][eo[i]++] = j;
	}

	int dd[N], pp[N], hh[N], gg[N];
	int ii[M], iii[M][K], kk[M], m;

	int dfs1(int p, int i, int d) {
		pp[i] = p, dd[i] = d;
		int s = 1;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				s += dfs1(i, j, d + 1);
		}
		if (s >= B || p == -1)
			ii[m++] = i, s = 0;
		return s;
	}

	void dfs2(int p, int i, int h) {
		if (hh[i] != -1)
			return;
		hh[i] = h, iii[h][gg[i] = kk[h]++] = i;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				dfs2(i, j, h);
		}
	}

	void init(vi uu, vi vv, int n_) {
		n = n_;
		memset(eo, 0, n * sizeof *eo);
		for (int h = 0; h < n - 1; h++)
			append(uu[h], vv[h]), append(vv[h], uu[h]);
		int i = 0;
		while (eo[i] > 2)
			i++;
		m = 0, dfs1(-1, i, 0);
		int tmp;
		for (int h1 = 0, h2 = m - 1; h1 < h2; h1++, h2--)
			tmp = ii[h1], ii[h1] = ii[h2], ii[h2] = tmp;
		memset(hh, -1, n * sizeof *hh);
		for (int h = m - 1; h >= 0; h--) {
			i = ii[h];
			kk[h] = 0, dfs2(pp[i], i, h);
		}
		for (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 bb) {
		int hu, hv; decode_pair(M, decode(bb, 0, L), hu, hv);
		if (hu == hv) {
			string cc((K - 1) * LK, '0');
			for (int g = 1; g < kk[hu]; g++)
				encode(cc, (g - 1) * LK, LK, gg[pp[iii[hu][g]]]);
			return cc;
		}
		int u = iii[hu][0], v = iii[hv][0];
		if (dist(u, v) == dd[v] - dd[u]) {
			int u_ = v;
			while (hh[u_] != hh[u])
				u_ = pp[u_];
			u = u_;
		}
		string cc(K * 2 * LK + LN, '0');
		for (int g = 0; g < kk[hu]; g++)
			encode(cc, g * LK, LK, dist(u, iii[hu][g]));
		for (int g = 0; g < kk[hv]; g++)
			encode(cc, (K + g) * LK, LK, dist(v, iii[hv][g]));
		encode(cc, K * 2 * LK, LN, dist(u, v));
		return cc;
	}
}

void Init(int n, vi ii, vi jj) {
	Ali::init(ii, jj, n);
}

string SendA(string bb) {
	return Ali::send(bb);
}

Benjamin

/* https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Benjamin.h"
#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;
	const int L = 20;
	const int LN = 14;	/* LN = ceil(log2(N)) */
	const int LK = 4;	/* LK = ceil(log2(K)) */

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

	void encode(string &aa, int i_, int n, int x) {
		for (int i = 0; i < n; i++)
			aa[i_ + i] = (x >> i & 1) + '0';
	}

	int decode(string &aa, int i_, int n) {
		int x = 0;
		for (int i = 0; i < n; i++)
			if (aa[i_ + i] == '1')
				x |= 1 << i;
		return x;
	}

	int encode_pair(int n, int i, int j) {
		return i * (n * 2 - i + 1) / 2 + j - i;
	}

	int n, hu, gu, hv, gv;

	string send(int n_, int u, int v) {
		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;
		string bb(L, '0');
		encode(bb, 0, L, encode_pair(M, hu, hv));
		return bb;
	}

	int pp[K];

	int answer(string aa) {
		if (hu == hv) {
			for (int g = 1; g < K; g++)
				pp[g] = decode(aa, (g - 1) * LK, LK);
			int d = 0;
			while (gu != gv) {
				d++;
				if (gu > gv)
					gu = pp[gu];
				else
					gv = pp[gv];
			}
			return d;
		}
		return decode(aa, gu * LK, LK) + decode(aa, (K + gv) * LK, LK) + decode(aa, K * 2 * LK, LN);
	}
}

string SendB(int n, int u, int v) {
	return Benjamin::send(n, u, v);
}

int Answer(string aa) {
	return Benjamin::answer(aa);
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

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