//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 |