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
//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);
}
//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];
      |        ^~~~~~~~
# 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
# 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