#include "Ali.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
namespace alice_tree {
const int N = 1e6 + 10;
int tree[N], x[30];
int cnt_tree;
void backtrack (int pos, int one, int h) {
// cerr << pos << " " << one << " " << h << endl;
if (one == 13) {
int mask = 0;
for(int i = 0; i < pos; i++) if (x[i]) mask |= (1 << i);
// if (mask == 16373) {
// for(int i = 0; i <= pos; i++) cout << x[i]; cout << endl;
// }
// for(int i = 0; i <= pos; i++) cout << x[i] << " "; cout << endl;
int cur = 0, cnt_id = 0;
vector<int> p(13, 0), cnt(13, 0);
for(int i = 0; i < pos; i++) {
// if (mask == 16373) cout << i << " " << cur << endl;
if (x[i] == 1) {
if (cnt[cur] >= 2) return;
cnt[cur]++;
p[++cnt_id] = cur;
cur = cnt_id;
}
else {
assert(cur);
cur = p[cur];
}
}
int result_mask = 0;
for(int i = 0; i < pos; i++) if (x[i]) result_mask |= (1 << i);
tree[cnt_tree++] = result_mask;
return;
}
if (h > 0) {
x[pos] = 0;
backtrack(pos + 1, one, h - 1);
}
x[pos] = 1;
backtrack(pos + 1, one + 1, h + 1);
}
void gen_tree () {
backtrack(0, 1, 0);
sort(tree, tree + cnt_tree);
}
int idx (int mask) {
return lower_bound(tree, tree + cnt_tree, mask) - tree;
}
}
namespace alice {
const int N = 1e4 + 10, B = 7;
int par[N], idx_in_group[N], d[N], id[N];
int group_mask[2010];
int n;
int root = 0;
bool in[N];
vector<int> adj[N], g[N];
int cnt_group;
long long encode (vector<int> a, vector<int> b) {
long long code = 0;
for(int j = 0; j < (int) a.size(); j++) {
code = code * b[j] + a[j];
}
return code;
}
vector<int> decode (long long code, vector<int> b) {
vector<int> a(b.size());
for(int j = b.size() - 1; j >= 0; j--) {
a[j] = code % b[j];
code /= b[j];
}
return a;
}
vector<int> dfs(int u) {
// cout << u << endl;
vector<int> cur;
cur.push_back(u);
for(int &v : adj[u]) if (v != par[u]) {
d[v] = d[u] + 1;
par[v] = u;
vector<int> tmp = dfs(v);
for(int &j : tmp) cur.push_back(j);
}
if (cur.size() >= 7 || u == root) {
g[cnt_group] = cur;
cnt_group++;
cur.clear();
}
return cur;
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
n = N;
cnt_group = 0;
for(int i = 0; i < n; i++) adj[i].clear(), g[i].clear();
for(int i = 0; i < n; i++) par[i] = 0;
for(int i = 0; i < n - 1; i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
for(int i = 0; i < n; i++) if (adj[i].size() == 1) root = i;
d[root] = 0;
par[root] = root;
dfs(root);
// exit(0);
// cout << cnt_group << endl;
assert(cnt_group <= 1429);
sort(g, g + cnt_group, [] (const vector<int> &x, vector<int> &y) {
return d[x[0]] < d[y[0]];
});
// for(int i = 0; i < cnt_group; i++) {
// for(int &j : g[i]) cout << j << " "; cout << endl;
// }
if (alice_tree::cnt_tree == 0) alice_tree::gen_tree();
// cout << alice_tree::cnt_tree << endl;
int total, one, get_mask, last;
auto calc = [&] (auto self, int u) -> void {
idx_in_group[u] = one++;
for(int &v : adj[u]) if (in[v] && v != par[u]) {
get_mask |= (1 << total);
total++;
last = total;
self(self, v);
}
total++;
};
for(int i = 0; i < cnt_group; i++) {
for(int &j : g[i]) in[j] = 1;
total = one = get_mask = last = 0;
calc(calc, g[i][0]);
total = last;
for(int j = g[i].size() + 1; j <= 13; j++) {
get_mask |= (1 << total);
total++;
}
// for(int j = 0; (1 << j) <= get_mask; j++) cout << (get_mask >> j & 1);
// cout << endl;
group_mask[i] = get_mask;
for(int &j : g[i]) in[j] = 0;
}
// for(int j = 0; j <= 20; j++) cout << (65227 >> j & 1); cout << endl;
for(int i = 0; i < cnt_group; i++) {
for(int &j : g[i]) {
id[j] = i * 14 + idx_in_group[j];
}
}
// for(int i = 0; i < n; i++) cout << id[i] << " "; cout << endl;
for(int i = 0; i < n; i++) {
// cout << id[i] << " ";
SetID(i, id[i]);
}
// cout << encode({1, 2, 3}, {3, 4, 5}) << endl;
// vector<int> tmp = decode(33, {3, 4, 5});
// for(int &j : tmp) cout << j << " ";
// exit(0);
}
std::string SendA(std::string S) {
int code = 0;
for(int j = 0; j < 20; j++) if (S[j] == '1') code |= (1 << j);
int X = -1, Y = -1;
for(int last = 0; last < 1429; last++) if (last * (last + 1) / 2 + last >= code) {
Y = last;
X = code - last * (last + 1) / 2;
break;
}
assert(X >= 0 && X <= Y && Y < 1429);
// cout << X << " " << Y << endl;
// exit(0);
vector<int> cnt(n, 0);
for(int &j : g[X]) cnt[j]++;
for(int &j : g[Y]) cnt[j]++;
for(int v = g[X][0];; v = par[v]) {
// cout << v << endl;
cnt[v]++;
if (v == root) break;
}
for(int v = g[Y][0];; v = par[v]) {
// cout << v << "@\n";
cnt[v]++;
if (v == root) break;
}
cnt[g[X][0]]--;
cnt[g[Y][0]]--;
// cout << cnt[3] << endl;
int lca = root;
for(int i = 0; i < n; i++) if (cnt[i] > 1) {
if (d[i] > d[lca]) lca = i;
}
int code_lca = 0, middle = g[X][0];
for(int &j : g[X]) {
if (j == lca) code_lca = idx_in_group[j], middle = j;
}
// cout << X << " " << Y << endl;
// cout << root << endl;
// cout << middle << " " << lca << " " << g[Y][0] << endl;
int dist = d[middle] + d[g[Y][0]] - 2 * d[lca];
// cout << dist << endl;
// cout << alice_tree::idx(group_mask[X]) << " " << alice_tree::idx(group_mask[Y]) << "@" << endl;
// cout << group_mask[X] << endl;
int tmp = alice_tree::idx(group_mask[X]);
// cout << alice_tree::tree[tmp] << endl;
// for(int j = 0; j < 20; j++) cout << (16373 >> j & 1); cout << endl;
// for(int j = 0; j < 20; j++) cout << (18431 >> j & 1); cout << endl;
// exit(0);
assert(group_mask[X] == alice_tree::tree[tmp]);
long long Code = encode({code_lca, dist, alice_tree::idx(group_mask[X]), alice_tree::idx(group_mask[Y])},
{13, n, alice_tree::cnt_tree, alice_tree::cnt_tree});
long long max_code = encode({12, n - 1, alice_tree::cnt_tree - 1, alice_tree::cnt_tree - 1},
{13, n, alice_tree::cnt_tree, alice_tree::cnt_tree});
// cout << Code << endl;
string ret;
for(int bit = 0; (1LL << bit) <= max_code; bit++) {
if (Code >> bit & 1) ret.push_back('1');
else ret.push_back('0');
}
return ret;
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
return alice::Init(N, U, V);
}
std::string SendA(std::string S) {
return alice::SendA(S);
}
#include "Benjamin.h"
#include<bits/stdc++.h>
using namespace std;
#include <string>
#include <vector>
namespace bruno_tree {
const int N = 1e6 + 10;
int tree[N], x[30];
int cnt_tree;
void backtrack (int pos, int one, int h) {
// cerr << pos << " " << one << " " << h << endl;
if (one == 13) {
// for(int i = 0; i <= pos; i++) cout << x[i] << " "; cout << endl;
int cur = 0, cnt_id = 0;
vector<int> p(13, 0), cnt(13, 0);
for(int i = 0; i < pos; i++) {
if (x[i] == 1) {
if (cnt[cur] >= 2) return;
cnt[cur]++;
p[++cnt_id] = cur;
cur = cnt_id;
}
else {
assert(cur);
cur = p[cur];
}
}
int result_mask = 0;
for(int i = 0; i < pos; i++) if (x[i]) result_mask |= (1 << i);
tree[cnt_tree++] = result_mask;
return;
}
if (h > 0) {
x[pos] = 0;
backtrack(pos + 1, one, h - 1);
}
x[pos] = 1;
backtrack(pos + 1, one + 1, h + 1);
}
void gen_tree () {
backtrack(0, 1, 0);
sort(tree, tree + cnt_tree);
}
int idx (int mask) {
return lower_bound(tree, tree + cnt_tree, mask) - tree;
}
}
struct tree {
int p[20];
vector<int> adj[20];
void extract (int mask) {
for(int i = 0; i < 20; i++) adj[i].clear();
int cnt_id = 0, cur = 0;
assert(mask >> 0 & 1);
for(int i = 0; (1 << i) <= mask; i++) {
if (mask >> i & 1 == 1) {
p[++cnt_id] = cur;
adj[cnt_id].push_back(cur);
adj[cur].push_back(cnt_id);
// cout << cnt_id << " " << cur << endl;
cur = cnt_id;
}
else {
assert(cur);
cur = p[cur];
}
}
}
int dist (int u, int pre, int destination) {
if (destination == u) return 0;
int ret = -1;
for(int &v : adj[u]) if (v != pre) {
int tmp = dist(v, u, destination);
if (tmp != -1) ret = tmp + 1;
}
return ret;
}
} tree1, tree2;
namespace bruno {
int x, y, X, Y;
int n;
long long encode (vector<int> a, vector<int> b) {
long long code = 0;
for(int j = 0; j < a.size(); j++) {
code = code * b[j] + a[j];
}
return code;
}
vector<int> decode (long long code, vector<int> b) {
vector<int> a(b.size());
for(int j = b.size() - 1; j >= 0; j--) {
a[j] = code % b[j];
code /= b[j];
}
return a;
}
std::string SendB(int N, int xx, int yy) {
n = N;
if (xx > yy) swap(xx, yy);
X = xx / 14;
Y = yy / 14;
x = xx % 14;
y = yy % 14;
// cout << X << " " << Y << "@" << endl;
int code = Y * (Y + 1) / 2 + X;
// cout << code << endl;
assert((1 << 20) > code);
string ret;
for(int j = 0; j < 20; j++) {
if (code >> j & 1) ret.push_back('1');
else ret.push_back('0');
}
return ret;
}
int Answer(std::string T) {
// exit(0);
if (bruno_tree::cnt_tree == 0) bruno_tree::gen_tree();
long long code = 0;
for(int j = 0; j < T.size(); j++) if (T[j] == '1') code |= (1LL << j);
vector<int> info = decode(code,
{13, n, bruno_tree::cnt_tree, bruno_tree::cnt_tree});
tree1.extract(bruno_tree::tree[info[2]]);
tree2.extract(bruno_tree::tree[info[3]]);
// cout << x << " " << y << endl;
// cout << bruno_tree::tree[info[2]] << endl;
if (X == Y) return tree1.dist(x, x, y);
// cout << 1 << endl;
// cout << info[2] << " " << info[3] << endl;
// cout << x << " " << y << endl;
// exit(0);
int middle = info[0];
int dist = info[1];
// cout << middle << " " << dist << endl;
// cout << tree1.dist(x, x, middle) << endl;
// cout << tree2.dist(y, y, 0) << endl;
// cout << y << endl;
// cout << dist << endl;
return tree1.dist(x, x, middle) + tree2.dist(y, y, 0) + dist;
}
}
std::string SendB(int N, int X, int Y) {
return bruno::SendB(N, X, Y);
}
int Answer(std::string T) {
return bruno::Answer(T);
}
Compilation message
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
10 | char _randmem[12379];
| ^~~~~~~~
Benjamin.cpp: In member function 'void tree::extract(int)':
Benjamin.cpp:68:23: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
68 | if (mask >> i & 1 == 1) {
| ~~^~~~
Benjamin.cpp: In function 'long long int bruno::encode(std::vector<int>, std::vector<int>)':
Benjamin.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j = 0; j < a.size(); j++) {
| ~~^~~~~~~~~~
Benjamin.cpp: In function 'int bruno::Answer(std::string)':
Benjamin.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int j = 0; j < T.size(); j++) if (T[j] == '1') code |= (1LL << j);
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3300 KB |
Output is correct |
2 |
Correct |
23 ms |
3244 KB |
Output is correct |
3 |
Correct |
23 ms |
3084 KB |
Output is correct |
4 |
Correct |
23 ms |
3088 KB |
Output is correct |
5 |
Correct |
23 ms |
3240 KB |
Output is correct |
6 |
Correct |
28 ms |
3932 KB |
Output is correct |
7 |
Correct |
30 ms |
3912 KB |
Output is correct |
8 |
Correct |
35 ms |
3952 KB |
Output is correct |
9 |
Correct |
29 ms |
4144 KB |
Output is correct |
10 |
Correct |
40 ms |
4412 KB |
Output is correct |
11 |
Correct |
27 ms |
3984 KB |
Output is correct |
12 |
Correct |
30 ms |
3996 KB |
Output is correct |
13 |
Correct |
27 ms |
3688 KB |
Output is correct |
14 |
Correct |
27 ms |
3948 KB |
Output is correct |
15 |
Correct |
28 ms |
5220 KB |
Output is correct |
16 |
Correct |
28 ms |
4056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
23 ms |
3252 KB |
Output is partially correct |
2 |
Partially correct |
72 ms |
6232 KB |
Output is partially correct |
3 |
Partially correct |
24 ms |
3252 KB |
Output is partially correct |
4 |
Partially correct |
246 ms |
4216 KB |
Output is partially correct |
5 |
Partially correct |
254 ms |
4448 KB |
Output is partially correct |
6 |
Partially correct |
250 ms |
4760 KB |
Output is partially correct |
7 |
Partially correct |
258 ms |
5784 KB |
Output is partially correct |
8 |
Partially correct |
234 ms |
4216 KB |
Output is partially correct |
9 |
Partially correct |
254 ms |
4852 KB |
Output is partially correct |
10 |
Partially correct |
234 ms |
5904 KB |
Output is partially correct |
11 |
Partially correct |
212 ms |
4428 KB |
Output is partially correct |
12 |
Partially correct |
51 ms |
4052 KB |
Output is partially correct |
13 |
Partially correct |
141 ms |
4364 KB |
Output is partially correct |
14 |
Partially correct |
151 ms |
4284 KB |
Output is partially correct |
15 |
Partially correct |
26 ms |
3820 KB |
Output is partially correct |
16 |
Partially correct |
228 ms |
5880 KB |
Output is partially correct |
17 |
Partially correct |
234 ms |
5856 KB |
Output is partially correct |
18 |
Partially correct |
234 ms |
5624 KB |
Output is partially correct |
19 |
Partially correct |
244 ms |
5844 KB |
Output is partially correct |
20 |
Partially correct |
149 ms |
5292 KB |
Output is partially correct |
21 |
Partially correct |
226 ms |
5604 KB |
Output is partially correct |
22 |
Partially correct |
215 ms |
4648 KB |
Output is partially correct |
23 |
Partially correct |
226 ms |
4712 KB |
Output is partially correct |
24 |
Partially correct |
225 ms |
4332 KB |
Output is partially correct |
25 |
Partially correct |
239 ms |
4412 KB |
Output is partially correct |
26 |
Partially correct |
219 ms |
4444 KB |
Output is partially correct |
27 |
Partially correct |
228 ms |
4184 KB |
Output is partially correct |
28 |
Partially correct |
211 ms |
4032 KB |
Output is partially correct |
29 |
Partially correct |
229 ms |
4520 KB |
Output is partially correct |
30 |
Partially correct |
211 ms |
4332 KB |
Output is partially correct |
31 |
Partially correct |
223 ms |
4132 KB |
Output is partially correct |
32 |
Partially correct |
215 ms |
4132 KB |
Output is partially correct |
33 |
Partially correct |
221 ms |
4328 KB |
Output is partially correct |
34 |
Partially correct |
205 ms |
4348 KB |
Output is partially correct |
35 |
Partially correct |
235 ms |
4616 KB |
Output is partially correct |
36 |
Partially correct |
220 ms |
4316 KB |
Output is partially correct |
37 |
Partially correct |
210 ms |
4288 KB |
Output is partially correct |
38 |
Partially correct |
204 ms |
4468 KB |
Output is partially correct |
39 |
Partially correct |
52 ms |
4196 KB |
Output is partially correct |
40 |
Partially correct |
250 ms |
5648 KB |
Output is partially correct |