Submission #1101246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101246		rainboy	Flights (JOI22_flights)	C++17	67 / 100	185 ms	2444 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; }

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

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

	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], hh[N], gg[N];
	int ii[M], iii[M][K], kk[M], m; string ss[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);
		}
		if (s >= B || p == -1) {
			ii[m++] = i, s = 0;
			if (p != -1)
				detach(p, i);
		}
		return s;
	}

	void dfs2(int i, int h) {
		hh[i] = h, iii[h][gg[i] = kk[h]++] = i;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			ss[h] += '0', dfs2(j, h), ss[h] += '1';
		}
	}

	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;
		for (int h = m - 1; h >= 0; h--) {
			i = ii[h];
			kk[h] = 0, ss[h].clear(), dfs2(i, h), ss[h].resize((K - 1) * 2, '0');
		}
		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 cc) {
		int hu, hv; decode_pair(M, decode(cc), hu, hv);
		if (hu == hv)
			return ss[hu];
		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_;
		}
		return ss[hu] + ss[hv] + encode(LK, gg[u]) + encode(LK, gg[v]) + 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 <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; }

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

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

	int decode_tree(string cc, int *pp) {
		int m = cc.size();
		while (m > 0 && cc[m - 1] == '0')
			m--;
		int n = 1, cnt = 0;
		pp[0] = -1, qu[cnt++] = 0;
		for (int h = 0; h < m; h++)
			if (cc[h] == '0')
				pp[n] = qu[cnt - 1], qu[cnt++] = n, n++;
			else
				cnt--;
		return 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 answer(string cc) {
		if (hu == hv) {
			decode_tree(cc, pp);
			return dist(pp, gu, gv);
		}
		decode_tree(string(cc, 0, (K - 1) * 2), ppu);
		decode_tree(string(cc, (K - 1) * 2, (K - 1) * 2), ppv);
		int gu_ = decode(string(cc, (K - 1) * 4, LK));
		int gv_ = decode(string(cc, (K - 1) * 4 + LK, LK));
		int d = decode(string(cc, (K - 1) * 4 + LK * 2, LN));
		return dist(ppu, gu, gu_) + d + dist(ppv, gv_, 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)

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

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