#include "Ali.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
const int MAXN = 1e4+5;
const int block = 20;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
int n;
vector<int> edges[MAXN];
int id[MAXN];
vector<int> has[MAXN];
int topo[MAXN]; // 0 down, 1 up
int dist[MAXN];
int par[MAXN];
int t = 0;
void reset() {
for (int i = 0; i < MAXN; i++) {
edges[i].clear();
id[i] = 0;
has[i].clear();
topo[i] = 0;
dist[i] = 0;
par[i] = 0;
}
t = 0;
}
string make_str(ll v, int pad = -1) {
string s = "";
while (v) {
s = ((char)('0'+(v&1)) + s);
v /= 2;
}
if (pad != -1) {
while (s.size() < pad) {
s = '0'+s;
}
}
return s;
}
ll make_int(string s) {
ll v = 0;
for (char c: s) {
v *= 2;
v += c-'0';
}
return v;
}
ll hsh(vector<pll> &code) {
ll ret = 0;
for (pll p: code) {
ret *= p.second;
ret += p.first;
}
return ret;
}
void inc(int &a, bool b) {
a = 2*a+b;
}
void dfs(int cur, int p = -1) {
id[cur] = t;
has[(t++)/block].push_back(cur);
for (int v: edges[cur]) {
if (v == p) continue;
inc(topo[(t-1)/block], 0);
dfs(v, cur);
has[(t++)/block].push_back(cur);
}
inc(topo[(t-1)/block], 1);
}
pll encode_dist(vector<int> nodes1, vector<int> nodes2) {
fill(dist, dist+n, MAXN);
fill(par, par+n, -1);
queue<int> vals;
for (int i = 0; i < nodes1.size(); i++) {
int v = nodes1[i];
dist[v] = 0;
vals.push(v);
par[v] = i;
}
while (!vals.empty()) {
int t = vals.front();
vals.pop();
for (int v: edges[t]) {
if (dist[v] < MAXN) continue;
dist[v] = 1+dist[t];
par[v] = par[t];
}
}
int b = 0;
for (int i = 1; i < nodes2.size(); i++) {
int v = nodes2[i];
if (dist[v] < dist[nodes2[b]]) b = i;
}
int a = par[nodes2[b]];
vector<pll> code;
code.push_back(pll(a, block));
code.push_back(pll(b, block));
code.push_back(pll(dist[b]/2, MAXN/2));
return pll(hsh(code), block*block*(MAXN/2));
}
}
void Init(int N, vector<int> u, vector<int> v) {
reset();
n = N;
for (int i = 0; i < n-1; i++) {
edges[u[i]].push_back(v[i]);
edges[v[i]].push_back(u[i]);
}
fill(id, id+n, -1);
for (int i = 0; i < n; i++) if (edges[i].size() < 3) {
dfs(i);
break;
}
for (int i = 0; i < n; i++) SetID(i, id[i]);
// variable_example++;
// SetID(0, 0);
// SetID(1, 1);
// SetID(2, 2 * N + 19);
}
string SendA(string S) {
int v = make_int(S);
int v1 = v >> 10;
int v2 = v % (1<<10);
// first, encode the trees (to be optimized)
vector<pll> code;
code.push_back(pll(topo[v1]/2, 1<<(block-1)));
code.push_back(pll(topo[v2]/2, 1<<(block-1)));
// get closest nodes
code.push_back(encode_dist(has[v1], has[v2]));
return make_str(hsh(code));
}
#include "Benjamin.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
const int MAXN = 1e4+5;
const int block = 20;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
vector<ll> szs({1<<(block-1), 1<<(block-1), block, block, MAXN/2});
int n, x, y;
vector<pii> edges[2*block];
int id[block+1];
void reset() {
for (int i = 0; i < 2*block; i++) edges[i].clear();
for (int i = 0; i <= block; i++) id[i] = 0;
}
string make_str(ll v, int pad = -1) {
string s = "";
while (v) {
s = ((char)('0'+(v&1)) + s);
v /= 2;
}
if (pad != -1) {
assert(s.size() <= pad);
while (s.size() < pad) {
s = '0'+s;
}
}
return s;
}
vector<ll> decode(ll hshed) {
vector<ll> res;
for (int i = szs.size()-1; i >= 0; i--) {
res.push_back(hshed % szs[i]);
hshed /= szs[i];
}
reverse(res.begin(), res.end());
return res;
}
ll make_int(string s) {
ll v = 0;
for (char c: s) {
v *= 2;
v += c-'0';
}
return v;
}
vector<int> stck;
void make_edge(int a, int b, int w) {
edges[a].push_back({b, w});
edges[b].push_back({a, w});
}
void build_tree(int inc, string s, int p = 0) {
if (p == 0) {
stck.clear();
stck.push_back(p);
}
id[p] = stck.back();
if (p == s.size()) return;
if (s[p] == '0') {
make_edge(inc+stck.back(), inc+p+1, 1);
stck.push_back(p+1);
build_tree(inc, s, p+1);
}
if (s[p] == '1') {
if (stck.size() == 1) {
make_edge(inc+stck.back(), inc+p+1, 1);
stck.pop_back();
stck.push_back(p+1);
}
else stck.pop_back();
build_tree(inc, s, p+1);
}
}
int get_dist(int cur, int tar, int p = -1) {
if (cur == tar) return 0;
for (pii e: edges[cur]) {
int nxt = e.first;
if (nxt == p) continue;
int v = get_dist(nxt, tar, cur);
if (v != -1) return v+e.second;
}
return -1;
}
}
string SendB(int N, int X, int Y) {
reset();
n = N;
x = X;
y = Y;
return make_str(x/block, 10)+make_str(y/block, 10);
}
int Answer(string T) {
ll v = make_int(T);
vector<ll> nums = decode(v);
build_tree(0, make_str(nums[0], min(19, 2*n-2-20*(x/20))));
nums[2] = id[nums[2]];
if (x/20 != y/20) {
build_tree(block, make_str(nums[1], min(19, 2*n-2-20*(y/20))));
nums[3] = id[nums[3]];
}
if (x/20 != y/20) make_edge(nums[2], nums[3]+block, 2*nums[4]+((nums[2]+nums[3])&1));
int ans = get_dist(x%20, ((x/20 == y/20) ? 0 : 20)+(y%20));
assert(ans != -1);
return ans;
}
Compilation message
Ali.cpp: In function 'std::string {anonymous}::make_str({anonymous}::ll, int)':
Ali.cpp:43:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
43 | while (s.size() < pad) {
| ~~~~~~~~~^~~~~
Ali.cpp: In function '{anonymous}::pll {anonymous}::encode_dist(std::vector<int>, std::vector<int>)':
Ali.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < nodes1.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Ali.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = 1; i < nodes2.size(); i++) {
| ~~^~~~~~~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
10 | char _randmem[12379];
| ^~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Benjamin.cpp:2:
Benjamin.cpp: In function 'std::string {anonymous}::make_str({anonymous}::ll, int)':
Benjamin.cpp:32:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | assert(s.size() <= pad);
| ~~~~~~~~~^~~~~~
Benjamin.cpp:33:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
33 | while (s.size() < pad) {
| ~~~~~~~~~^~~~~
Benjamin.cpp: In function 'void {anonymous}::build_tree(int, std::string, int)':
Benjamin.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if (p == s.size()) return;
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1808 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1428 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1636 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1640 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
1612 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
1652 KB |
Output is partially correct |
| 2 |
Incorrect |
5 ms |
1644 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
