Submission #560515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
560515	2022-05-11T15:06:28 Z	DanShaders	Flights (JOI22_flights)	C++17	93 / 100	423 ms	5312 KB

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

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

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2704 KB	Output is correct
2	Correct	2 ms	2704 KB	Output is correct
3	Correct	2 ms	2704 KB	Output is correct
4	Correct	2 ms	2704 KB	Output is correct
5	Correct	2 ms	2704 KB	Output is correct
6	Correct	13 ms	3728 KB	Output is correct
7	Correct	11 ms	3772 KB	Output is correct
8	Correct	11 ms	3848 KB	Output is correct
9	Correct	11 ms	3780 KB	Output is correct
10	Correct	12 ms	4092 KB	Output is correct
11	Correct	8 ms	3708 KB	Output is correct
12	Correct	9 ms	3652 KB	Output is correct
13	Correct	8 ms	3644 KB	Output is correct
14	Correct	9 ms	4036 KB	Output is correct
15	Correct	11 ms	4736 KB	Output is correct
16	Correct	10 ms	3776 KB	Output is correct

Subtask #2

78.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	2 ms	2704 KB	Output is partially correct
2	Partially correct	80 ms	5032 KB	Output is partially correct
3	Partially correct	7 ms	2704 KB	Output is partially correct
4	Partially correct	404 ms	4484 KB	Output is partially correct
5	Partially correct	423 ms	4300 KB	Output is partially correct
6	Partially correct	396 ms	4368 KB	Output is partially correct
7	Partially correct	368 ms	5312 KB	Output is partially correct
8	Partially correct	396 ms	4440 KB	Output is partially correct
9	Partially correct	307 ms	4964 KB	Output is partially correct
10	Partially correct	299 ms	5076 KB	Output is partially correct
11	Partially correct	402 ms	4392 KB	Output is partially correct
12	Partially correct	45 ms	3880 KB	Output is partially correct
13	Partially correct	197 ms	4664 KB	Output is partially correct
14	Partially correct	214 ms	4448 KB	Output is partially correct
15	Partially correct	8 ms	2832 KB	Output is partially correct
16	Partially correct	293 ms	4832 KB	Output is partially correct
17	Partially correct	318 ms	4996 KB	Output is partially correct
18	Partially correct	336 ms	5124 KB	Output is partially correct
19	Partially correct	310 ms	5004 KB	Output is partially correct
20	Partially correct	212 ms	5044 KB	Output is partially correct
21	Partially correct	357 ms	5084 KB	Output is partially correct
22	Partially correct	302 ms	3820 KB	Output is partially correct
23	Partially correct	275 ms	4028 KB	Output is partially correct
24	Partially correct	275 ms	3788 KB	Output is partially correct
25	Partially correct	264 ms	3728 KB	Output is partially correct
26	Partially correct	267 ms	3772 KB	Output is partially correct
27	Partially correct	294 ms	3892 KB	Output is partially correct
28	Partially correct	274 ms	3744 KB	Output is partially correct
29	Partially correct	262 ms	3776 KB	Output is partially correct
30	Partially correct	283 ms	3852 KB	Output is partially correct
31	Partially correct	265 ms	3764 KB	Output is partially correct
32	Partially correct	257 ms	3724 KB	Output is partially correct
33	Partially correct	278 ms	3784 KB	Output is partially correct
34	Partially correct	274 ms	3952 KB	Output is partially correct
35	Partially correct	263 ms	3708 KB	Output is partially correct
36	Partially correct	260 ms	3772 KB	Output is partially correct
37	Partially correct	272 ms	3952 KB	Output is partially correct
38	Partially correct	275 ms	3824 KB	Output is partially correct
39	Partially correct	50 ms	3644 KB	Output is partially correct
40	Partially correct	401 ms	5208 KB	Output is partially correct