oj.uz

Submission #560500

# Submission time Handle Problem Language Result Execution time Memory
560500 2022-05-11T14:36:47 Z DanShaders Flights (JOI22_flights) C++17
0 / 100
 3 ms 2716 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 = 20010;

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 < 2 * 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[0]]} < pair{csz[cchild[1]], tour[cchild[1]]}
		) {
			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[0]]} < pair{csz[cchild[1]], tour[cchild[1]]}
		) {
			reverse(all(cchild));
			reverse(all(g[u]));
		}

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

	// cout << "using root " << root << endl;
	// for (int i = 0; i < nnext; ++i) {
	// 	cout << i << " " << tour[i] << " " << root_cnt[i] << ": ";
	// 	for (int j : g[i]) {
	// 		cout << j << " ";
	// 	}
	// 	cout << "\n";
	// }

	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) {
	// 	cout << ids[i] << " ";
	// }
	// cout << endl;
	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;
		}
	}
	// cout << cx << " " << cy << endl;
	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));
	int ox = ids[cx] - x * 14, oy = ids[cy] - y * 14;
	// cout << tx << " " << ty << " " << ox << " " << oy << " " << dst << endl;

	ostringstream out;
	out << bitset<14>(dst);
	out << bitset<4>(ox) << bitset<4>(oy);
	out << bitset<7>(tx) << bitset<7>(ty);
	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 dst = int(bitset<14>(t.substr(0, 14)).to_ulong()),
		ox = int(bitset<4>(t.substr(14, 4)).to_ulong()),
		oy = int(bitset<4>(t.substr(18, 4)).to_ulong()),
		tx = int(bitset<7>(t.substr(22, 7)).to_ulong()),
		ty = int(bitset<7>(t.substr(29, 7)).to_ulong());
	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 = 20010;

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 < 2 * 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[0]]} < pair{csz[cchild[1]], tour[cchild[1]]}
		) {
			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[0]]} < pair{csz[cchild[1]], tour[cchild[1]]}
		) {
			reverse(all(cchild));
			reverse(all(g[u]));
		}

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

	// cout << "using root " << root << endl;
	// for (int i = 0; i < nnext; ++i) {
	// 	cout << i << " " << tour[i] << " " << root_cnt[i] << ": ";
	// 	for (int j : g[i]) {
	// 		cout << j << " ";
	// 	}
	// 	cout << "\n";
	// }

	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) {
	// 	cout << ids[i] << " ";
	// }
	// cout << endl;
	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;
		}
	}
	// cout << cx << " " << cy << endl;
	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));
	int ox = ids[cx] - x * 14, oy = ids[cy] - y * 14;
	// cout << tx << " " << ty << " " << ox << " " << oy << " " << dst << endl;

	ostringstream out;
	out << bitset<14>(dst);
	out << bitset<4>(ox) << bitset<4>(oy);
	out << bitset<7>(tx) << bitset<7>(ty);
	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 dst = int(bitset<14>(t.substr(0, 14)).to_ulong()),
		ox = int(bitset<4>(t.substr(14, 4)).to_ulong()),
		oy = int(bitset<4>(t.substr(18, 4)).to_ulong()),
		tx = int(bitset<7>(t.substr(22, 7)).to_ulong()),
		ty = int(bitset<7>(t.substr(29, 7)).to_ulong());
	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2704 KB Output is correct
2 Correct 3 ms 2704 KB Output is correct
3 Correct 3 ms 2716 KB Output is correct
4 Correct 2 ms 2712 KB Output is correct
5 Incorrect 1 ms 1352 KB Incorrect
6 Halted 0 ms 0 KB -

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 2704 KB Output is partially correct
2 Incorrect 1 ms 1404 KB Incorrect
3 Halted 0 ms 0 KB -