Submission #560515

#	Time	Username	Problem	Language	Result	Execution time	Memory
560515		DanShaders	Flights (JOI22_flights)	C++17	93 / 100	423 ms	5312 KiB

Ali

//bs:sanitizers,flags:grader.cpp
#include "Ali.h"
#include "Benjamin.h"

void setID(int p, int value) {
	(void) p;
	(void) value;
	SetID(p, value);
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 20040;

int n;
vector<int> g[N];
int parent[N], sz[N], csz[N];
string tour[N];
int root_cnt[N];
vector<int> order;

int dfs_order(int u, int p = -1) {
	sz[u] = 1;
	parent[u] = p;
	for (int v : g[u]) {
		if (v != p) {
			sz[u] += dfs_order(v, u);
		}
	}
	order.push_back(u);
	return sz[u];
}

int get_forward(int x, int y) {
	return y * (y + 1) / 2 + x;
}

pair<int, int> get_backward(int num) {
	int lef = 0, rig = n;
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (mid * (mid + 1) / 2 <= num) {
			lef = mid;
		} else {
			rig = mid;
		}
	}
	return {num - lef * (lef + 1) / 2, lef};
}

const string BASE[] = {
	"(((((())))))",
	"((((()()))))",
	"((((())())))",
	"((((()))()))",
	"((((())))())",
	"(((()())()))",
	"(((()()))())",
	"(((())(())))",
	"(((())())())",
	"(((()))(()))",
	"((()())(()))",
};

vector<string> BASE2;

int ids[N];
int comp[N];

void dfs_id(int u, int cnts, int &cnt) {
	comp[u] = cnts;
	ids[u] = cnts * 14 + cnt++;
	for (int v : g[u]) {
		if (parent[u] != v && root_cnt[v] == -1) {
			dfs_id(v, cnts, cnt);
		}
	}
}

void init_base2() {
	if (!sz(BASE2)) {
		for (int i = 0; i < 11; ++i) {
			for (int j = i; j < 11; ++j) {
				BASE2.push_back("("s + BASE[i] + BASE[j] + ")");
			}
		}
	}
}

void Init(int n_, vector<int> us, vector<int> vs) {
	init_base2();
	n = n_;
	int nmax = 2 * n + 19;
	for (int i = 0; i < nmax; ++i) {
		g[i].clear();
	}
	order.clear();

	for (int i = 0; i < n - 1; ++i) {
		g[us[i]].push_back(vs[i]);
		g[vs[i]].push_back(us[i]);
	}
	
	int root = -1;
	for (int i = 0; i < n; ++i) {
		if (sz(g[i]) <= 2) {
			root = i;
			break;
		}
	}
	dfs_order(root);
	int root_it = 0;

	int nnext = n;
	auto new_node = [&](int p) {
		parent[nnext] = p;
		root_cnt[nnext] = -1;
		csz[nnext] = 1;
		g[p].push_back(nnext);
		return nnext++;
	};

	for (int u : order) {
		root_cnt[u] = -1;
		csz[u] = 1;
		vector<int> cchild;
		for (int v : g[u]) {
			if (root_cnt[v] == -1 && v != parent[u]) {
				cchild.push_back(v);
				csz[u] += csz[v];
			}
		}
		if (sz(cchild) > 1 &&
			pair{csz[cchild[0]], tour[cchild[1]]} < pair{csz[cchild[1]], tour[cchild[0]]}
		) {
			swap(cchild[0], cchild[1]);
			reverse(all(g[u]));
		}
		tour[u] = "("s +
			(sz(cchild) > 0 ? tour[cchild[0]] : "") +
			(sz(cchild) > 1 ? tour[cchild[1]] : "") + ")";
		if (csz[u] >= 7 || u == root) {
			root_cnt[u] = root_it++;
			while (sz(cchild) < 2) {
				++csz[u];
				cchild.push_back(new_node(u));
			}
			while (csz[u] != 13) {
				int curr = -1;
				for (int v : cchild) {
					if (csz[v] < 6) {
						curr = v;
						break;
					}
				}
				assert(curr != -1);
				while (1) {
					++csz[curr];
					int nxt = -1;
					for (int v : g[curr]) {
						if (v != parent[curr] && root_cnt[v] == -1) {
							nxt = v;
							break;
						}
					}
					if (nxt == -1) {
						new_node(curr);
						break;
					} else {
						curr = nxt;
					}
				}
				++csz[u];
			}
		}
	}
	for (int i = nnext; i >= n; --i) {
		tour[i] = "(";
		for (int j : g[i]) {
			tour[i] += tour[j];
		}
		tour[i] += ")";
	}
	for (int u : order) {
		vector<int> cchild;
		for (int v : g[u]) {
			if (parent[u] != v && root_cnt[v] == -1) {
				cchild.push_back(v);
			}
		}
		if (sz(cchild) > 1 &&
			pair{csz[cchild[0]], tour[cchild[1]]} < pair{csz[cchild[1]], tour[cchild[0]]}
		) {
			reverse(all(cchild));
			reverse(all(g[u]));
		}

		tour[u] = "(";
		for (int v : cchild) {
			tour[u] += tour[v];
		}
		tour[u] += ")";
	}

	for (int i = 0; i < n; ++i) {
		if (root_cnt[i] != -1) {
			int cnt = 0;
			dfs_id(i, root_cnt[i], cnt);
			assert(cnt == 13);
		}
	}
	for (int i = 0; i < n; ++i) {
		setID(i, ids[i]);
	}
}

vector<int> path;

int dfs(int u, int w, int p = -1) {
	path.push_back(u);
	if (u == w) {
		return 0;
	}
	for (int v : g[u]) {
		if (v != p) {
			int ans = dfs(v, w, u);
			if (ans != -1) {
				return ans + 1;
			}
		}
	}
	path.pop_back();
	return -1;
}

string SendA(string s) {
	auto [x, y] = get_backward((int) bitset<20>(s).to_ulong());
	int xroot = int(find(root_cnt, root_cnt + n, x) - root_cnt),
		yroot = int(find(root_cnt, root_cnt + n, y) - root_cnt);
	path.clear();
	dfs(xroot, yroot);
	int cx = -1, cy = -1;
	for (int u : path) {
		if (comp[u] == x) {
			cx = u;
		}
		if (comp[u] == y && cy == -1) {
			cy = u;
		}
	}
	int dst = dfs(cx, cy);
	int tx = int(find(all(BASE2), tour[xroot]) - begin(BASE2));
	int ty = int(find(all(BASE2), tour[yroot]) - begin(BASE2));
	assert(tx != sz(BASE2) && ty != sz(BASE2));
	int ox = ids[cx] - x * 14, oy = ids[cy] - y * 14;
	bool is_first = !ox;
	int which = is_first ? oy : ox;

	// cout << dst << " " << tx << " " << ty << " " << ox << " " << oy << " " << is_first << " " << which << endl;

	ostringstream out;
	out << bitset<31>(
		dst + 10000 * (
		tx + 66 * (
		ty + 66 * (
		is_first + 2 * (
		which)))));
	return out.str();
}

int x, y;

string SendB(int n_, int x_, int y_) {
	n = n_, x = x_, y = y_;
	if (x > y) {
		swap(x, y);
	}

	int xb = x / 14, yb = y / 14;
	ostringstream out;
	out << bitset<20>(get_forward(xb, yb));
	return out.str();
}

vector<vector<int>> get_tree(int i) {
	vector<vector<int>> res(14);
	int curr = -1;
	int it = 1;

	for (char c : BASE2[i]) {
		if (c == '(') {
			if (curr == -1) {
				curr = 0;
			} else {
				res[it].push_back(curr);
				res[curr].push_back(it);
				curr = it++;
			}
		} else if (curr) {
			curr = res[curr][0];
		}
	}
	return res;
}

int dfs_dist(const vector<vector<int>> &t, int u, int w, int p = -1) {
	if (u == w) {
		return 0;
	}

	for (int v : t[u]) {
		if (v != p) {
			int ans = dfs_dist(t, v, w, u);
			if (ans != -1) {
				return ans + 1;
			}
		}
	}
	return -1;
}

int Answer(string t) {
	init_base2();
	int val = int(bitset<31>(t).to_ulong());
	int dst = val % 10000; val /= 10000;
	int tx = val % 66; val /= 66;
	int ty = val % 66; val /= 66;
	int is_first = val % 2; val /= 2;
	int which = val;
	int ox = 0, oy = 0;
	
	if (is_first) {
		oy = which;
	} else {
		ox = which;
	}

	// cout << dst << " " << tx << " " << ty << " " << ox << " " << oy << " " << is_first << " " << which << endl;

	if (x / 14 == y / 14) {
		return dfs_dist(get_tree(tx), x % 14, y % 14);
	}
	// cout << ox << " " << oy << " " << tx << " " << ty << " " << dst << endl;
	// cout << dfs_dist(get_tree(ty), oy, y % 14) << endl;
	return dst + dfs_dist(get_tree(tx), ox, x % 14) + dfs_dist(get_tree(ty), oy, y % 14);
}

Benjamin

//bs:sanitizers,flags:grader.cpp
#include "Ali.h"
#include "Benjamin.h"

void setID(int p, int value) {
	(void) p;
	(void) value;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 20040;

int n;
vector<int> g[N];
int parent[N], sz[N], csz[N];
string tour[N];
int root_cnt[N];
vector<int> order;

int dfs_order(int u, int p = -1) {
	sz[u] = 1;
	parent[u] = p;
	for (int v : g[u]) {
		if (v != p) {
			sz[u] += dfs_order(v, u);
		}
	}
	order.push_back(u);
	return sz[u];
}

int get_forward(int x, int y) {
	return y * (y + 1) / 2 + x;
}

pair<int, int> get_backward(int num) {
	int lef = 0, rig = n;
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (mid * (mid + 1) / 2 <= num) {
			lef = mid;
		} else {
			rig = mid;
		}
	}
	return {num - lef * (lef + 1) / 2, lef};
}

const string BASE[] = {
	"(((((())))))",
	"((((()()))))",
	"((((())())))",
	"((((()))()))",
	"((((())))())",
	"(((()())()))",
	"(((()()))())",
	"(((())(())))",
	"(((())())())",
	"(((()))(()))",
	"((()())(()))",
};

vector<string> BASE2;

int ids[N];
int comp[N];

void dfs_id(int u, int cnts, int &cnt) {
	comp[u] = cnts;
	ids[u] = cnts * 14 + cnt++;
	for (int v : g[u]) {
		if (parent[u] != v && root_cnt[v] == -1) {
			dfs_id(v, cnts, cnt);
		}
	}
}

void init_base2() {
	if (!sz(BASE2)) {
		for (int i = 0; i < 11; ++i) {
			for (int j = i; j < 11; ++j) {
				BASE2.push_back("("s + BASE[i] + BASE[j] + ")");
			}
		}
	}
}

void Init(int n_, vector<int> us, vector<int> vs) {
	init_base2();
	n = n_;
	int nmax = 2 * n + 19;
	for (int i = 0; i < nmax; ++i) {
		g[i].clear();
	}
	order.clear();

	for (int i = 0; i < n - 1; ++i) {
		g[us[i]].push_back(vs[i]);
		g[vs[i]].push_back(us[i]);
	}
	
	int root = -1;
	for (int i = 0; i < n; ++i) {
		if (sz(g[i]) <= 2) {
			root = i;
			break;
		}
	}
	dfs_order(root);
	int root_it = 0;

	int nnext = n;
	auto new_node = [&](int p) {
		parent[nnext] = p;
		root_cnt[nnext] = -1;
		csz[nnext] = 1;
		g[p].push_back(nnext);
		return nnext++;
	};

	for (int u : order) {
		root_cnt[u] = -1;
		csz[u] = 1;
		vector<int> cchild;
		for (int v : g[u]) {
			if (root_cnt[v] == -1 && v != parent[u]) {
				cchild.push_back(v);
				csz[u] += csz[v];
			}
		}
		if (sz(cchild) > 1 &&
			pair{csz[cchild[0]], tour[cchild[1]]} < pair{csz[cchild[1]], tour[cchild[0]]}
		) {
			swap(cchild[0], cchild[1]);
			reverse(all(g[u]));
		}
		tour[u] = "("s +
			(sz(cchild) > 0 ? tour[cchild[0]] : "") +
			(sz(cchild) > 1 ? tour[cchild[1]] : "") + ")";
		if (csz[u] >= 7 || u == root) {
			root_cnt[u] = root_it++;
			while (sz(cchild) < 2) {
				++csz[u];
				cchild.push_back(new_node(u));
			}
			while (csz[u] != 13) {
				int curr = -1;
				for (int v : cchild) {
					if (csz[v] < 6) {
						curr = v;
						break;
					}
				}
				assert(curr != -1);
				while (1) {
					++csz[curr];
					int nxt = -1;
					for (int v : g[curr]) {
						if (v != parent[curr] && root_cnt[v] == -1) {
							nxt = v;
							break;
						}
					}
					if (nxt == -1) {
						new_node(curr);
						break;
					} else {
						curr = nxt;
					}
				}
				++csz[u];
			}
		}
	}
	for (int i = nnext; i >= n; --i) {
		tour[i] = "(";
		for (int j : g[i]) {
			tour[i] += tour[j];
		}
		tour[i] += ")";
	}
	for (int u : order) {
		vector<int> cchild;
		for (int v : g[u]) {
			if (parent[u] != v && root_cnt[v] == -1) {
				cchild.push_back(v);
			}
		}
		if (sz(cchild) > 1 &&
			pair{csz[cchild[0]], tour[cchild[1]]} < pair{csz[cchild[1]], tour[cchild[0]]}
		) {
			reverse(all(cchild));
			reverse(all(g[u]));
		}

		tour[u] = "(";
		for (int v : cchild) {
			tour[u] += tour[v];
		}
		tour[u] += ")";
	}

	for (int i = 0; i < n; ++i) {
		if (root_cnt[i] != -1) {
			int cnt = 0;
			dfs_id(i, root_cnt[i], cnt);
			assert(cnt == 13);
		}
	}
	for (int i = 0; i < n; ++i) {
		setID(i, ids[i]);
	}
}

vector<int> path;

int dfs(int u, int w, int p = -1) {
	path.push_back(u);
	if (u == w) {
		return 0;
	}
	for (int v : g[u]) {
		if (v != p) {
			int ans = dfs(v, w, u);
			if (ans != -1) {
				return ans + 1;
			}
		}
	}
	path.pop_back();
	return -1;
}

string SendA(string s) {
	auto [x, y] = get_backward((int) bitset<20>(s).to_ulong());
	int xroot = int(find(root_cnt, root_cnt + n, x) - root_cnt),
		yroot = int(find(root_cnt, root_cnt + n, y) - root_cnt);
	path.clear();
	dfs(xroot, yroot);
	int cx = -1, cy = -1;
	for (int u : path) {
		if (comp[u] == x) {
			cx = u;
		}
		if (comp[u] == y && cy == -1) {
			cy = u;
		}
	}
	int dst = dfs(cx, cy);
	int tx = int(find(all(BASE2), tour[xroot]) - begin(BASE2));
	int ty = int(find(all(BASE2), tour[yroot]) - begin(BASE2));
	assert(tx != sz(BASE2) && ty != sz(BASE2));
	int ox = ids[cx] - x * 14, oy = ids[cy] - y * 14;
	bool is_first = !ox;
	int which = is_first ? oy : ox;

	// cout << dst << " " << tx << " " << ty << " " << ox << " " << oy << " " << is_first << " " << which << endl;

	ostringstream out;
	out << bitset<31>(
		dst + 10000 * (
		tx + 66 * (
		ty + 66 * (
		is_first + 2 * (
		which)))));
	return out.str();
}

int x, y;

string SendB(int n_, int x_, int y_) {
	n = n_, x = x_, y = y_;
	if (x > y) {
		swap(x, y);
	}

	int xb = x / 14, yb = y / 14;
	ostringstream out;
	out << bitset<20>(get_forward(xb, yb));
	return out.str();
}

vector<vector<int>> get_tree(int i) {
	vector<vector<int>> res(14);
	int curr = -1;
	int it = 1;

	for (char c : BASE2[i]) {
		if (c == '(') {
			if (curr == -1) {
				curr = 0;
			} else {
				res[it].push_back(curr);
				res[curr].push_back(it);
				curr = it++;
			}
		} else if (curr) {
			curr = res[curr][0];
		}
	}
	return res;
}

int dfs_dist(const vector<vector<int>> &t, int u, int w, int p = -1) {
	if (u == w) {
		return 0;
	}

	for (int v : t[u]) {
		if (v != p) {
			int ans = dfs_dist(t, v, w, u);
			if (ans != -1) {
				return ans + 1;
			}
		}
	}
	return -1;
}

int Answer(string t) {
	init_base2();
	int val = int(bitset<31>(t).to_ulong());
	int dst = val % 10000; val /= 10000;
	int tx = val % 66; val /= 66;
	int ty = val % 66; val /= 66;
	int is_first = val % 2; val /= 2;
	int which = val;
	int ox = 0, oy = 0;
	
	if (is_first) {
		oy = which;
	} else {
		ox = which;
	}

	// cout << dst << " " << tx << " " << ty << " " << ox << " " << oy << " " << is_first << " " << which << endl;

	if (x / 14 == y / 14) {
		return dfs_dist(get_tree(tx), x % 14, y % 14);
	}
	// cout << ox << " " << oy << " " << tx << " " << ty << " " << dst << endl;
	// cout << dfs_dist(get_tree(ty), oy, y % 14) << endl;
	return dst + dfs_dist(get_tree(tx), ox, x % 14) + dfs_dist(get_tree(ty), oy, y % 14);
}

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: 78 / 85