QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #884303 | #3505. Flights | duongnc000 | 0 | 3ms | 4224kb | C++20 | 20.1kb | 2025-02-05 23:41:05 | 2025-02-05 23:41:06 |
Judging History
Ali
#include "Ali.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;
namespace {
int N, nn;
vector<bool> ig;
vector<vector<pair<int, int>>> g;
vector<vector<int>> group;
vector<pair<int, int>> lab;
vector<int> par, dep, sz, lst, trr, head;
vector<string> sub_hash;
map<string, pair<vector<vector<int>>, pair<vector<int>, int>>> fake_shit;
map<string, pair<vector<vector<int>>, pair<int, int>>> real_shit;
map<vector<int>, int> mp;
vector<string> six = {
"000011001111",
"000010110111",
"000001110111",
"000000111111",
"000001011111",
"000011100111",
"000101100111",
"000011011011",
"000001111011",
"000001101111",
"000010111011",
};
vector<int> add = {3, 3, 2, 3, 4, 1, 2, 5, 2, 0, 3};
int dfs1(int u, int p) {
int sz = 1;
for (auto [v, id] : g[u]) if (v != p) {
dep[v] = dep[u] + 1;
int val = dfs1(v, u);
if (val >= 7) ig[id] = true;
else sz += val;
}
return sz;
}
void new_node() {
g.emplace_back();
ig.emplace_back(0);
trr.emplace_back(-1);
lab.emplace_back(-1, -1);
sub_hash.emplace_back("");
}
void get_group(int u, int p) {
sz[u] = 1;
lab[u] = {isz(group) - 1, isz(group.back())};
group.back().emplace_back(u);
for (auto [v, id] : g[u]) if (v != p and id < N - 1 and not ig[id]) {
par[v] = lab[u].second;
get_group(v, u);
sz[u] += sz[v];
lst[u] = lst[v];
}
if (lst[u] == -1) lst[u] = u;
}
void add_nodes(int u) {
int cnt = 0;
for (auto [v, id] : g[u]) if (not ig[id]) {
++cnt;
int clst = lst[v];
while (sz[v] < 6) {
new_node();
g[clst].emplace_back(nn, nn - 1);
g[nn].emplace_back(clst, nn - 1);
clst = nn, sz[v]++, nn++;
}
}
while (cnt < 2) {
int clst = u;
for (int i = 0; i < 6; ++i) {
new_node();
g[clst].emplace_back(nn, nn - 1);
g[nn].emplace_back(clst, nn - 1);
clst = nn, nn++;
}
++cnt;
}
}
int get_centroid() {
vector<int> sz(N);
auto dfs_sz = [&](auto self, int u, int p) -> void {
sz[u] = 1;
for (auto [v, id] : g[u]) if (v != p) {
self(self, v, u);
sz[u] += sz[v];
}
};
dfs_sz(dfs_sz, 0, -1);
auto dfs_cen = [&](auto self, int u, int p) -> int {
for (auto [v, id] : g[u]) if (v != p) {
if (sz[v] > sz[0] / 2) return self(self, v, u);
}
return u;
};
int root = dfs_cen(dfs_cen, 0, -1);
queue<int> q;
vector<int> vis(N);
q.emplace(root);
vis[root] = true;
while (not q.empty()) {
int u = q.front();
if (isz(g[u]) < 3) {
root = u;
break;
}
q.pop();
for (auto [v, id] : g[u]) if (not vis[v]) {
q.emplace(v);
vis[v] = true;
}
}
vis.assign(N, -1);
q = queue<int>();
vis[root] = 0;
q.emplace(root);
while (not q.empty()) {
int u = q.front();
q.pop();
for (auto [v, id] : g[u]) if (vis[v] == -1) {
vis[v] = vis[u] + 1;
q.emplace(v);
}
}
assert(*max_element(all(vis)) <= 5000);
return root;
}
int callitacheck(int u, int p) {
int sz = 1;
vector<int> vec;
for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
int val = callitacheck(v, u);
if (p == -1) vec.emplace_back(val);
sz += val;
}
if (p == -1) {
sort(all(vec));
assert(vec[0] == 6);
assert(vec[1] == 7);
assert(sz == 14);
}
return sz;
}
// bool print;
string get_hash(int u, int p) {
vector<string> vec;
for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
// if (print) cout << v << " <-> " << u << endl;
vec.push_back(get_hash(v, u));
}
sort(all(vec));
string res = "";
res.push_back('0');
for (auto s : vec) res += s;
res.push_back('1');
return sub_hash[u] = res;
};
void relabel_dfs(int u, int p, int &cnt) {
// cout << u << " = " << cnt << endl;
lab[u].second = cnt++;
vector<pair<string, int>> vec;
for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
vec.push_back({sub_hash[v], v});
}
sort(all(vec));
for (auto [_, v] : vec) {
relabel_dfs(v, u, cnt);
}
}
void add_to_make_7(int u, int p, int tp) {
// print = true;
// cout << get_hash(u, p) << endl;
// print = false;
queue<int> q;
q.emplace(u);
while (not q.empty()) {
int u = q.front(); q.pop();
if (lab[u].second == add[tp]) {
// int deg = 0;
// for (auto [v, id] : g[u]) if (not ig[id]) ++deg;
// assert(deg < 3);
// cout << u << endl;
new_node();
g[u].emplace_back(nn, nn - 1);
g[nn].emplace_back(u, nn - 1);
nn++;
break;
}
for (auto [v, id] : g[u]) if (v != p and not ig[id] and lab[v].second > lab[u].second) {
q.emplace(v);
}
}
}
void relabel_bfs(int u) {
queue<array<int, 3>> q;
q.push({u, -1, 0});
vector<pair<int, pair<string, int>>> vec;
while (not q.empty()) {
auto [u, p, d] = q.front(); q.pop();
vec.push_back({d, {sub_hash[u], u}});
for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
q.push({v, u, d + 1});
}
}
group.back().clear();
sort(all(vec));
for (auto tmp : vec) {
int u = tmp.second.second;
lab[u].first = isz(group) - 1;
lab[u].second = isz(group.back());
group.back().emplace_back(u);
}
}
array<int, 3> bfs(int gX, int gY) {
queue<int> q;
vector<int> trace(nn, -1), d(nn, -1);
d[group[gX][0]] = 0;
q.emplace(group[gX][0]);
while (not q.empty()) {
auto u = q.front(); q.pop();
if (lab[u].first == gY) {
int len = 0, ou = u;
while (lab[u].first != gX) {
u = trace[u];
++len;
}
return {u, ou, len};
}
for (auto [v, id] : g[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
trace[v] = u;
q.emplace(v);
}
}
}
}
void dfs2(int u, int p, int d) {
lab[u].first = d;
for (auto [v, id] : g[u]) if (v != p and not ig[id]) {
dfs2(v, u, d + 1);
}
}
void process() {
auto add_edge = [&](auto &g, int u, int v) -> void {
g[u].emplace_back(v);
g[v].emplace_back(u);
};
auto get_dist = [&](const auto &g, int root) -> vector<int> {
queue<int> q;
vector<int> d(isz(g), -1);
q.emplace(root);
d[root] = 0;
while (not q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) if (d[v] == -1) {
d[v] = d[u] + 1;
q.emplace(v);
}
}
sort(all(d));
return d;
};
auto get_hash = [&](auto &self, auto &g, int u, int p) -> string {
vector<string> vec;
for (auto v : g[u]) if (v != p) {
vec.push_back(self(self, g, v, u));
}
sort(all(vec));
string res = "";
res.push_back('0');
for (auto s : vec) res += s;
res.push_back('1');
return res;
};
for (int i = 0; i < isz(six); ++i) {
vector<vector<int>> g(6);
stack<int> st;
int cur = -1;
st.push(cur++);
for (char ch : six[i]) {
if (ch == '0') {
int p = st.top();
st.push(cur++);
if (p != -1) {
add_edge(g, p, st.top());
}
}
else {
st.pop();
}
}
}
for (int i = 0; i < isz(six); ++i) for (int j = i; j < isz(six); ++j) {
vector<vector<int>> g(14);
int cur = 1;
stack<int> st; st.push(0);
for (char ch : six[i]) {
if (ch == '0') {
int p = st.top();
st.push(cur++);
add_edge(g, p, st.top());
}
else {
st.pop();
}
}
assert(cur == 7);
for (char ch : six[j]) {
if (ch == '0') {
int p = st.top();
st.push(cur++);
add_edge(g, p, st.top());
}
else {
st.pop();
}
}
add_edge(g, 7 + add[j], cur++);
assert(st.top() == 0 and cur == 14);
auto dist = get_dist(g, 0);
if (not mp.count(dist)) mp[dist] = isz(mp);
fake_shit[get_hash(get_hash, g, 0, -1)] = {g, {dist, isz(fake_shit)}};
for (int i = 0; i < 14; ++i) if (isz(g[i]) < 3) {
auto str = get_hash(get_hash, g, i, -1);
if (not real_shit.count(str)) real_shit[str] = {g, {i, isz(real_shit)}};
}
}
}
string encode(int ans) {
int len = 1;
assert(ans < (1 << 25) - 2);
while (ans >= (1 << len)) {
ans -= (1 << len);
++len;
}
assert(len < 25);
string res = "";
for (int i = 0; i < len; ++i) {
res.push_back((ans >> i & 1) + '0');
}
return res;
}
}
void Init(int N, vector<int> U, vector<int> V) {
::N = N;
g.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
int u = U[i], v = V[i];
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
dep.assign(N, 0);
ig.assign(N - 1, false);
int root = get_centroid();
dfs1(root, -1);
nn = N;
vector<int> avec(N);
iota(all(avec), 0);
sort(all(avec), [&](int x, int y) {
return dep[x] < dep[y];
});
group.clear();
sz.assign(N, 0);
lst.assign(N, -1);
par.assign(N, -1);
trr.assign(N, -1);
sub_hash.assign(N, "");
lab.assign(N, {-1, -1});
for (int i : avec) if (lab[i].first == -1) {
// cout << i << endl;
head.emplace_back(i);
group.emplace_back();
get_group(i, -1);
add_nodes(i);
vector<pair<int, int>> wai;
int cnt_child = 0;
for (auto [v, id] : g[i]) if (not ig[id]) {
++cnt_child;
auto str = get_hash(v, i);
int idx = find(all(six), str) - six.begin();
wai.emplace_back(idx, v);
assert(idx < isz(six));
int tmp = 0;
relabel_dfs(v, i, tmp);
}
assert(cnt_child == 2);
sort(all(wai));
// cout << wai[1].second << " " << i << " " << wai[1].first << endl;
add_to_make_7(wai[1].second, i, wai[1].first);
get_hash(i, -1);
relabel_bfs(i);
callitacheck(i, -1);
}
for (int i = 0; i < N; ++i) {
// cout << i << " " << lab[i].first * 13 + lab[i].second << endl;
SetID(i, lab[i].first * 14 + lab[i].second);
}
}
string SendA(string S) {
int val = 0, cnt = 0;
for (int i = 0; i < 20; ++i) {
val += (S[i] - '0') << i;
}
int gX = -1, gY = -1;
for (int i = 0; i < 1429; ++i) for (int j = i; j < 1429; ++j) {
if (val == cnt) gX = i, gY = j;
++cnt;
}
// cout << -1 << endl;
// return "11";
process();
if (gX == gY) {
auto str = get_hash(head[gX], -1);
assert(fake_shit.count(str));
int idx = fake_shit[str].second.second;
string res = "";
for (int i = 0; i < 5; ++i) res.push_back((idx >> i & 1) + '0');
return res;
}
auto [vX, vY, len] = bfs(gX, gY);
// assert(gX <= gY);
int ans = 0;
if (len <= 5000) {
assert(vY == head[gY]);
auto strX = get_hash(vX, -1);
auto strY = get_hash(vY, -1);
assert(real_shit.count(strX));
assert(fake_shit.count(strY));
auto distY = fake_shit[strY].second.first;
assert(mp.count(distY));
ans += (len - 1) * 288 * 21 + real_shit[strX].second.second * 21 + mp[distY];
assert(ans < 5000 * 288 * 21);
}
else {
ans += 5000 * 288 * 21;
assert(vX == head[gX]);
assert(vY == head[gY]);
auto strX = get_hash(vX, -1);
auto strY = get_hash(vY, -1);
assert(fake_shit.count(strX));
assert(fake_shit.count(strY));
auto distX = fake_shit[strX].second.first;
auto distY = fake_shit[strY].second.first;
assert(mp.count(distX));
assert(mp.count(distY));
ans += (len - 5001) * 21 * 21 + mp[distX] * 21 + mp[distY];
}
// cout << ans << endl;
return encode(ans);
// dfs2(vX, -1, 0); dfs2(vY, -1, 0);
// string res = "";
// sort(all(group[gX]), [&](const auto &lhs, const auto &rhs) {
// return lab[lhs].second < lab[rhs].second;
// });
// for (auto u : group[gX]) for (int i = 0; i < 4; ++i) {
// res.push_back((lab[u].first >> i & 1) + '0');
// }
// while (isz(res) < 52) res.push_back('0');
// sort(all(group[gY]), [&](const auto &lhs, const auto &rhs) {
// return lab[lhs].second < lab[rhs].second;
// });
// for (auto u : group[gY]) for (int i = 0; i < 4; ++i) {
// res.push_back((lab[u].first >> i & 1) + '0');
// }
// while (isz(res) < 104) res.push_back('0');
// for (int i = 0; i < 14; ++i) {
// res.push_back((len >> i & 1) + '0');
// }
// return res;
}
Benjamin
#include "Benjamin.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;
namespace {
int gX, nX, gY, nY;
map<string, pair<vector<vector<int>>, pair<vector<int>, int>>> fake_shit;
map<string, pair<vector<vector<int>>, pair<int, int>>> real_shit;
map<vector<int>, int> mp;
vector<string> six = {
"000011001111",
"000010110111",
"000001110111",
"000000111111",
"000001011111",
"000011100111",
"000101100111",
"000011011011",
"000001111011",
"000001101111",
"000010111011",
};
vector<int> add = {3, 3, 2, 3, 4, 1, 2, 5, 2, 0, 3};
void process() {
auto add_edge = [&](auto &g, int u, int v) -> void {
g[u].emplace_back(v);
g[v].emplace_back(u);
};
auto get_dist = [&](const auto &g, int root) -> vector<int> {
queue<int> q;
vector<int> d(isz(g), -1);
q.emplace(root);
d[root] = 0;
while (not q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) if (d[v] == -1) {
d[v] = d[u] + 1;
q.emplace(v);
}
}
sort(all(d));
return d;
};
auto get_hash = [&](auto &self, auto &g, int u, int p) -> string {
vector<string> vec;
for (auto v : g[u]) if (v != p) {
vec.push_back(self(self, g, v, u));
}
sort(all(vec));
string res = "";
res.push_back('0');
for (auto s : vec) res += s;
res.push_back('1');
return res;
};
for (int i = 0; i < isz(six); ++i) {
vector<vector<int>> g(6);
stack<int> st;
int cur = -1;
st.push(cur++);
for (char ch : six[i]) {
if (ch == '0') {
int p = st.top();
st.push(cur++);
if (p != -1) {
add_edge(g, p, st.top());
}
}
else {
st.pop();
}
}
}
for (int i = 0; i < isz(six); ++i) for (int j = i; j < isz(six); ++j) {
vector<vector<int>> g(14);
int cur = 1;
stack<int> st; st.push(0);
for (char ch : six[i]) {
if (ch == '0') {
int p = st.top();
st.push(cur++);
add_edge(g, p, st.top());
}
else {
st.pop();
}
}
assert(cur == 7);
for (char ch : six[j]) {
if (ch == '0') {
int p = st.top();
st.push(cur++);
add_edge(g, p, st.top());
}
else {
st.pop();
}
}
add_edge(g, 7 + add[j], cur++);
assert(st.top() == 0 and cur == 14);
auto dist = get_dist(g, 0);
if (not mp.count(dist)) mp[dist] = isz(mp);
fake_shit[get_hash(get_hash, g, 0, -1)] = {g, {dist, isz(fake_shit)}};
for (int i = 0; i < 14; ++i) if (isz(g[i]) < 3) {
auto str = get_hash(get_hash, g, i, -1);
if (not real_shit.count(str)) real_shit[str] = {g, {i, isz(real_shit)}};
}
}
}
vector<int> get_label(const vector<vector<int>> &g) {
vector<string> sub_hash(isz(g));
auto get_hash = [&](auto self, int u, int p) -> string {
vector<string> vec;
for (auto v : g[u]) if (v != p) {
vec.push_back(self(self, v, u));
}
sort(all(vec));
string res = "";
res.push_back('0');
for (auto s : vec) res += s;
res.push_back('1');
return sub_hash[u] = res;
};
get_hash(get_hash, 0, -1);
vector<int> nl(isz(g));
queue<array<int, 3>> q;
q.push({0, -1, 0});
vector<pair<int, pair<string, int>>> vec;
while (not q.empty()) {
auto [u, p, d] = q.front(); q.pop();
vec.push_back({d, {sub_hash[u], u}});
for (auto v : g[u]) if (v != p) {
q.push({v, u, d + 1});
}
}
sort(all(vec));
for (int i = 0; i < isz(vec); ++i) {
nl[i] = vec[i].second.second;
}
return nl;
}
int bfs(const vector<vector<int>> &g, int st, int en) {
queue<int> q;
vector<int> d(isz(g), -1);
d[st] = 0; q.emplace(st);
while (not q.empty()) {
int u = q.front(); q.pop();
for (auto v : g[u]) if (d[v] == -1) {
d[v] = d[u] + 1;
q.emplace(v);
}
}
return d[en];
}
}
string SendB(int N, int X, int Y) {
if (X > Y) swap(X, Y);
gX = X / 14, nX = X % 14;
gY = Y / 14, nY = Y % 14;
int val = -1, cnt = 0;
for (int i = 0; i < 1429; ++i) for (int j = i; j < 1429; ++j) {
if (i == gX and j == gY) val = cnt;
++cnt;
}
string res = "";
for (int i = 0; i < 20; ++i) {
res.push_back((val >> i & 1) + '0');
}
return res;
}
int Answer(string T) {
process();
if (gX == gY) {
int grp = 0;
for (int i = 0; i < 5; ++i) {
grp += (T[i] - '0') << i;
}
vector<vector<int>> g;
for (auto [_, tmp] : fake_shit) if (tmp.second.second == grp) {
g = tmp.first;
}
assert(isz(g) == 14);
auto nl = get_label(g);
return bfs(g, nl[nX], nl[nY]);
}
// cout << gX << " " << gY << " " << nX << " " << nY << endl;
int enc = 0;
for (int i = 1; i < isz(T); ++i) {
enc += 1 << i;
}
for (int i = 0; i < isz(T); ++i) {
enc += (T[i] - '0') << i;
}
// cout << enc << endl;
int res = 0;
if (enc < 5000 * 288 * 21) {
int len = enc / (288 * 21) + 1; enc %= 288 * 21;
res += len;
int tpX = enc / 21; enc %= 21;
for (auto [_, tmp] : real_shit) if (tmp.second.second == tpX) {
auto g = tmp.first;
auto root = tmp.second.first;
auto nl = get_label(g);
res += bfs(g, root, nl[nX]);
break;
}
int tpY = enc;
for (auto [dist, idx] : mp) if (idx == tpY) {
res += dist[nY];
break;
}
}
else {
int len = enc / (21 * 21) + 5001; enc %= 21 * 21;
res += len;
int tpX = enc / 21; enc %= 21;
for (auto [dist, idx] : mp) if (idx == tpX) {
res += dist[nX];
break;
}
int tpY = enc;
for (auto [dist, idx] : mp) if (idx == tpY) {
res += dist[nY];
break;
}
}
return res;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 15
Accepted
time: 2ms
memory: 4096kb
input:
1 2 2 0 01110
output:
00000000000000000000 1
input:
output:
1 5
result:
points 1.0 L = 5 (test case 1)
Test #2:
score: 15
Accepted
time: 1ms
memory: 3968kb
input:
1 3 1 2 01110
output:
00000000000000000000 2
input:
output:
2 5
result:
points 1.0 L = 5 (test case 1)
Test #3:
score: 15
Accepted
time: 2ms
memory: 3840kb
input:
1 4 1 0 01110
output:
00000000000000000000 1
input:
output:
1 5
result:
points 1.0 L = 5 (test case 1)
Test #4:
score: 15
Accepted
time: 3ms
memory: 3968kb
input:
1 5 4 2 00001
output:
00000000000000000000 1
input:
output:
1 5
result:
points 1.0 L = 5 (test case 1)
Test #5:
score: 15
Accepted
time: 3ms
memory: 3968kb
input:
1 10000 5784 15710 10110010110110100
output:
00001011111011011110 28
input:
output:
28 17
result:
points 1.0 L = 17 (test case 1)
Test #6:
score: 15
Accepted
time: 1ms
memory: 4096kb
input:
1 10000 12390 1758 0100110110100001
output:
11001110011110010100 20
input:
output:
20 16
result:
points 1.0 L = 16 (test case 1)
Test #7:
score: 15
Accepted
time: 1ms
memory: 3968kb
input:
1 10000 12544 10839 01010111010011100
output:
10010110000010100011 29
input:
output:
29 17
result:
points 1.0 L = 17 (test case 1)
Test #8:
score: 15
Accepted
time: 2ms
memory: 3968kb
input:
1 10000 13679 7449 10110100100001010
output:
11000101110011101001 31
input:
output:
31 17
result:
points 1.0 L = 17 (test case 1)
Test #9:
score: 15
Accepted
time: 3ms
memory: 4096kb
input:
1 10000 6492 8170 11110001101001011010
output:
01010100111011100001 240
input:
output:
240 20
result:
points 1.0 L = 20 (test case 1)
Test #10:
score: 15
Accepted
time: 2ms
memory: 3968kb
input:
1 8191 12812 2327 1001000001101011
output:
00110000001101101100 23
input:
output:
23 16
result:
points 1.0 L = 16 (test case 1)
Test #11:
score: 15
Accepted
time: 1ms
memory: 4096kb
input:
1 9996 6309 4571 100101100001011000
output:
11010010101100100110 54
input:
output:
54 18
result:
points 1.0 L = 18 (test case 1)
Test #12:
score: 15
Accepted
time: 2ms
memory: 4096kb
input:
1 9996 7899 11049 100110111111000001
output:
11101111000001111001 70
input:
output:
70 18
result:
points 1.0 L = 18 (test case 1)
Test #13:
score: 15
Accepted
time: 3ms
memory: 3968kb
input:
1 10000 10410 10382 1111111110001000000
output:
10001010100111111101 96
input:
output:
96 19
result:
points 1.0 L = 19 (test case 1)
Test #14:
score: 0
Wrong Answer
time: 2ms
memory: 4224kb
input:
1 10000 19990 20004 001110110101111101110111
output:
10100100111010011111 78568
input:
output:
78568 24
result:
wrong answer Incorrect answer: read 78568 but expected 9999 (test case 1)
Subtask #2:
score: 0
Interactor Runtime Error
Test #16:
score: 0
Interactor Runtime Error
input:
15 2 0 2 01110 3 1 0 00111 4 2 1 00111 5 4 0
output:
00000000000000000000 1 00000000000000000000 1 00000000000000000000 2 00000000000000000000