#include "Aoi.h"
#include "bits/stdc++.h"
using i64 = long long;
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr i64 inf = i64(1E18);
std::string encode(i64 x, int b) {
assert(x < (1LL << b));
std::string res = "";
for (int i = 0; i < b; ++i) {
res += char('0' + (x >> i & 1));
}
return res;
}
i64 fac(int n) {
i64 res = 1;
for (int i = 1; i <= n; ++i) {
res *= i;
}
return res;
}
i64 factor_number(std::vector<int> p) {
int n = int(p.size());
if (n == 0) {
return 0;
}
i64 res = 0;
for (int i = 0; i < p[0]; ++i) {
res += fac(n - 1);
}
for (int i = 1; i < n; ++i) {
if (p[i] > p[0]) {
p[i] -= 1;
}
}
p.erase(p.begin());
res += factor_number(p);
assert(res < fac(n));
return res;
}
} // namespace
std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
std::vector<int> B, std::vector<i64> C,
std::vector<int> T, std::vector<int> X) {
std::string s;
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[A[i]].emplace_back(i);
adj[B[i]].emplace_back(i);
}
std::vector<i64> dis(N, inf);
min_pq<std::pair<i64, int>> que;
std::vector<int> prv(N, -1);
que.emplace(dis[0] = 0, 0);
while (!que.empty()) {
auto[d, v] = que.top();
que.pop();
if (d != dis[v]) {
continue;
}
for (auto i : adj[v]) {
int u = A[i] ^ B[i] ^ v;
if (chmin(dis[u], d + C[i])) {
prv[u] = i;
que.emplace(dis[u], u);
}
}
}
std::vector<std::vector<int>> tree(N);
for (int v = 1; v < N; ++v) {
int u = A[prv[v]] ^ B[prv[v]] ^ v;
debug(u, v);
tree[u].emplace_back(v);
}
int tim = 0;
std::vector<int> tin(N);
std::vector<int> tout(N);
std::vector<int> dep(N);
auto dfs1 = [&](auto&& self, int v) -> void {
tin[v] = tim++;
for (auto u : tree[v]) {
dep[u] = dep[v] + 1;
self(self, u);
}
tout[v] = tim;
};
dfs1(dfs1, 0);
std::vector<int> ord(Q);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
return tin[T[lhs]] < tin[T[rhs]];
});
debug(ord);
debug(factor_number(ord));
s += encode(factor_number(ord), 45);
std::vector<std::vector<int>> sub(N);
for (int i = 0; i < Q; ++i) {
sub[T[ord[i]]].emplace_back(i);
}
std::vector<std::pair<int, int>> g;
auto transform = [&](auto&& self, int v) -> std::pair<int, int> {
// debug(v);
std::vector<std::pair<int, int>> vec;
if (!sub[v].empty()) {
for (int i = sub[v].front(); i <= sub[v].back(); ++i) {
g.emplace_back(sub[v].front(), i);
}
vec.emplace_back(sub[v].front(), sub[v].back());
}
for (auto u : tree[v]) {
auto r = self(self, u);
if (r.first != -1) {
vec.emplace_back(r);
}
}
if (vec.empty()) {
return {-1, -1};
}
std::sort(vec.begin(), vec.end());
for (int i = 1; i < int(vec.size()); ++i) {
g.emplace_back(vec[0].first, vec[i].second);
}
return {vec.front().first, vec.back().second};
};
transform(transform, 0);
std::sort(g.begin(), g.end(), [&](auto lhs, auto rhs) -> bool {
if (lhs.second - lhs.first == rhs.second - rhs.first) {
return lhs.first < rhs.first;
}
return lhs.second - lhs.first < rhs.second - rhs.first;
});
debug(g);
assert(int(g.size()) == 2 * Q - 1);
std::vector<std::array<int, 2>> bin(2 * Q - 1, {-1, -1});
for (int i = Q; i < 2 * Q - 1; ++i) {
for (int j = 0; j < i; ++j) {
if (g[j].first == g[i].first) {
std::pair<int, int> oth = {g[j].second + 1, g[i].second};
int k = std::find(g.begin(), g.end(), oth) - g.begin();
if (k != 2 * Q - 1) {
bin[i] = {j, k};
}
}
}
}
std::vector<i64> f(Q + 1);
f[1] = 1;
for (int i = 2; i <= Q; ++i) {
for (int j = 1; j < i; ++j) {
f[i] += f[j] * f[i - j];
}
}
auto encode_catalan = [&](auto&& self, int v) -> i64 {
if (g[v].first == g[v].second) {
return 0;
}
i64 id_tree = 0;
int lc = bin[v][0];
int rc = bin[v][1];
int s = g[v].second - g[v].first + 1;
int sl = g[lc].second - g[lc].first + 1;
int sr = g[rc].second - g[rc].first + 1;
for (int i = 1; i < sl; ++i) {
id_tree += f[i] * f[s - i];
}
id_tree += self(self, lc) * f[sr];
id_tree += self(self, rc);
assert(id_tree < f[s]);
return id_tree;
};
i64 id_tree = encode_catalan(encode_catalan, 2 * Q - 2);
debug(id_tree);
s += encode(id_tree, 24);
std::vector<std::vector<int>> add(K);
for (int i = 0; i < Q; ++i) {
int v = T[ord[i]];
while (v != 0) {
int e = prv[v];
int ide = std::find(X.begin(), X.end(), e) - X.begin();
if (ide != K) {
add[ide].emplace_back(i);
}
v = A[e] ^ B[e] ^ v;
}
}
for (auto v : add) {
debug(v);
if (v.empty()) {
debug(31);
s += encode(31, 5);
} else {
int l = v.front();
int r = v.back();
int id = int(std::find(g.begin(), g.end(), std::pair{l, r}) - g.begin());
debug(id);
s += encode(id, 5);
}
}
debug();
debug();
debug();
return s;
}
#include "Bitaro.h"
#include "bits/stdc++.h"
using i64 = long long;
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr i64 inf = i64(1E18);
i64 decode(std::string s) {
i64 res = 0;
for (int i = 0; i < int(s.size()); ++i) {
if (s[i] == '1') {
res += 1LL << i;
}
}
return res;
}
i64 fac(int n) {
i64 res = 1;
for (int i = 1; i <= n; ++i) {
res *= i;
}
return res;
}
std::vector<int> decode_factor(int n, i64 x) {
if (n == 0) {
assert(x == 0);
return {};
}
assert(x < fac(n));
std::vector<int> p;
for (int i = 0; i < n; ++i) {
if (x >= fac(n - 1)) {
x -= fac(n - 1);
} else {
p.emplace_back(i);
auto q = decode_factor(n - 1, x);
for (auto& j : q) {
if (j >= i) {
j += 1;
}
}
p.insert(p.end(), q.begin(), q.end());
break;
}
}
return p;
}
} // namespace
void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
std::vector<i64> C, std::vector<int> T, std::vector<int> X,
std::string s) {
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[A[i]].emplace_back(i);
adj[B[i]].emplace_back(i);
}
i64 ord_number = decode(s.substr(0, 45));
s = s.substr(45);
debug(ord_number);
std::vector<int> ord = decode_factor(Q, ord_number);
debug(ord);
std::vector<i64> f(Q + 1);
f[1] = 1;
for (int i = 2; i <= Q; ++i) {
for (int j = 1; j < i; ++j) {
f[i] += f[j] * f[i - j];
}
}
i64 id_tree = decode(s.substr(0, 24));
debug(id_tree);
s = s.substr(24);
std::vector<std::pair<int, int>> g(2 * Q - 1);
int p = 2 * Q - 2;
std::vector<std::array<int, 2>> bin(2 * Q - 1, {-1, -1});
auto decode_catalan = [&](auto&& self, int v, i64 x) -> void {
if (g[v].first == g[v].second) {
assert(x == 0);
return;
}
int s = g[v].second - g[v].first + 1;
assert(x < f[s]);
int lc = --p;
int rc = --p;
bin[v] = {lc, rc};
for (int i = 1; i < s; ++i) {
debug(i);
if (x >= f[i] * f[s - i]) {
x -= f[i] * f[s - i];
} else {
debug(g[v], i);
g[lc] = {g[v].first, g[v].first + i - 1};
g[rc] = {g[v].first + i, g[v].second};
self(self, lc, x / f[s - i]);
self(self, rc, x % f[s - i]);
return;
}
}
};
g[2 * Q - 2] = {0, Q - 1};
decode_catalan(decode_catalan, 2 * Q - 2, id_tree);
std::sort(g.begin(), g.end(), [&](auto lhs, auto rhs) -> bool {
if (lhs.second - lhs.first == rhs.second - rhs.first) {
return lhs.first < rhs.first;
}
return lhs.second - lhs.first < rhs.second - rhs.first;
});
debug(g);
std::vector<std::vector<int>> st(N);
std::vector<std::vector<int>> add(K);
for (int i = 0; i < K; ++i) {
int id = decode(s.substr(0, 5));
debug(id);
if (id == 31) {
debug("emp");
// empty
} else {
int l = g[id].first;
int r = g[id].second;
for (int j = l; j <= r; ++j) {
st[T[ord[j]]].emplace_back(X[i]);
}
debug(l, r);
}
s = s.substr(5);
}
assert(s.empty());
debug(st);
for (auto ask_v : T) {
debug(ask_v, st[ask_v]);
auto cst = C;
for (auto i : X) {
cst[i] = inf;
}
for (auto i : st[ask_v]) {
cst[i] = 0;
}
std::vector<i64> dis(N, inf);
std::vector<int> prv(N, -1);
min_pq<std::pair<i64, int>> que;
que.emplace(dis[0] = 0, 0);
while (!que.empty()) {
auto[d, v] = que.top();
que.pop();
if (d != dis[v]) {
continue;
}
for (auto i : adj[v]) {
int u = A[i] ^ B[i] ^ v;
if (chmin(dis[u], d + cst[i])) {
prv[u] = i;
que.emplace(dis[u], u);
}
}
}
std::vector<int> res;
int v = ask_v;
while (v != 0) {
res.emplace_back(prv[v]);
v = A[prv[v]] ^ B[prv[v]] ^ v;
}
std::reverse(res.begin(), res.end());
answer(res);
}
}
