#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 inc_ll(ll &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], MAXN));
return pll(hsh(code), (ll)block*block*MAXN);
}
}
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;
bool com = 0;
pii inter;
for (int j = 0; j < has[v2].size(); j++) {
for (int i = 0; i < has[v1].size(); i++) {
if (has[v1][i] == has[v2][j]) {
inter = pii(i, j);
com = 1;
break;
}
}
if (com) break;
}
// code.push_back(pll(com, 2));
code.push_back(pll(topo[v1]/2, 1<<(block-1)));
code.push_back(pll(topo[v2]/2, 1<<(block-1)));
if (com && v1 != v2) {
// now we just need to specify the first joining point.
code.push_back(pll(inter.first, block));
code.push_back(pll(inter.second, block));
// and now, we are done!
return '1'+make_str(hsh(code));
}
// get closest nodes
code.push_back(encode_dist(has[v1], has[v2]));
return '0'+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> szs1({1<<(block-1), 1<<(block-1), block, block, MAXN});
vector<ll> szs2({1<<(block-1), 1<<(block-1), block, block});
int n, x, y;
vector<pii> edges[2*block];
int id[block+1];
vector<int> cpy_stck;
vector<int> stck;
void reset() {
for (int i = 0; i < 2*block; i++) edges[i].clear();
for (int i = 0; i <= block; i++) id[i] = 0;
cpy_stck.clear();
}
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> szs) {
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;
}
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, int lo = -1) {
if (p == 0) {
stck.clear();
stck.push_back(inc+p);
}
if (p == lo) {
if (cpy_stck.empty()) cpy_stck = stck;
else {
make_edge(cpy_stck.back(), stck.back(), 0);
stck = cpy_stck;
}
}
id[p] = stck.back();
if (p == s.size()) return;
if (s[p] == '0') {
make_edge(stck.back(), inc+p+1, 1);
stck.push_back(inc+p+1);
build_tree(inc, s, p+1, lo);
}
if (s[p] == '1') {
if (stck.size() == 1) {
make_edge(stck.back(), inc+p+1, 1);
stck.pop_back();
stck.push_back(inc+p+1);
}
else stck.pop_back();
build_tree(inc, s, p+1, lo);
}
}
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.substr(1));
if (T[0] == '0') {
vector<ll> nums = decode(v, szs1);
build_tree(0, make_str(nums[0], min(19, 2*n-2-20*(x/20))));
nums[2] = id[nums[2]];
bool same_comp = (x/20 == y/20);
x = id[x%20];
if (!same_comp) {
build_tree(block, make_str(nums[1], min(19, 2*n-2-20*(y/20))));
nums[3] = id[nums[3]];
make_edge(nums[2], nums[3], nums[4]);
}
y = id[y%20];
int ans = get_dist(x, y);
assert(ans != -1);
return ans;
}
else {
assert(false);
vector<ll> nums = decode(v, szs2);
build_tree(0, make_str(nums[0], min(19, 2*n-2-20*(x/20))), 0, nums[2]);
x = id[x%20];
build_tree(block, make_str(nums[1], min(19, 2*n-2-20*(y/20))), 0, nums[3]);
y = id[y%20];
int ans = get_dist(x, y);
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:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < nodes1.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Ali.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int i = 1; i < nodes2.size(); i++) {
| ~~^~~~~~~~~~~~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for (int j = 0; j < has[v2].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
Ali.cpp:150:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int i = 0; i < has[v1].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
Ali.cpp: At global scope:
Ali.cpp:72:6: warning: 'void {anonymous}::inc_ll({anonymous}::ll&, bool)' defined but not used [-Wunused-function]
72 | void inc_ll(ll &a, bool b){
| ^~~~~~
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:37:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | assert(s.size() <= pad);
| ~~~~~~~~~^~~~~~
Benjamin.cpp:38:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
38 | while (s.size() < pad) {
| ~~~~~~~~~^~~~~
Benjamin.cpp: In function 'void {anonymous}::build_tree(int, std::string, int, int)':
Benjamin.cpp:82:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if (p == s.size()) return;
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1648 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1648 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1644 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
1724 KB |
Incorrect |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
2 ms |
1652 KB |
Output is partially correct |
| 2 |
Incorrect |
5 ms |
1892 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
