#include <algorithm>
#include <cassert>
#include "multi.h"
void chmin(auto& a, auto b) { if (a > b) a = b; }
using namespace std;
using u64 = unsigned long long;
/*
- 3 倍 フェーズ (r = 1)
i -> j に送るもの:
- i から出る 1st min の辺の行き先 (8 bit)
- i から出る 2nd min の辺の (行き先, 重み) (56 bit)
1st min が双方向なら 2nd min を採用できる．
採用された 2nd min の重みは頂点 0 が数える．採用された 1st min の重みは，両端のどちらかが数える．
- Borůvka フェーズ (2 ≤ r ≤ 3)
i -> i に送るもの:
- i を含む連結成分の代表元 (8 bit)
- 現在の数えているコスト (56 bit)
i -> j に送るもの:
- i を含む連結成分の代表元 (8 bit)
- i - (i と連結でない頂点) の min の (行き先, 重み) (56 bit)
- 集約フェーズ (r = 4)
i -> 0 に送るもの:
- i を含む連結成分の代表元 (8 bit)
- 現在の確定したコストの総和 (56 bit)
i -> j に送るもの:
- i を含む連結成分の代表元 (8 bit)
- i - (j を含む連結成分) の min 重み (48 bit)
- 放送フェーズ (r = 5)
0 -> j に送るもの:
- i を含む連結成分の代表元 (8 bit)
- 現在の確定したコストの総和 (56 bit)
i -> j に送るもの:
- i を含む連結成分の代表元 (8 bit)
- 各連結成分を 1 頂点に圧縮する．自身から出る辺の中で kth min の辺の (重み, 行き先) (56 bit)
- k は自身の連結成分で何番目の頂点か
- 頂点 0 はこの送信を行わない (k は頂点 0 を無視して数える)
- k 番目の辺は存在しないかも (INF を送信する)
- 解答フェーズ
頂点 0 は Kruskal 法で答えを求める．
*/
struct Pack {
u64 uf : 8;
u64 j : 8;
u64 weight : 48;
};
struct Pack1 {
u64 first : 8;
u64 second : 8;
u64 weight : 48;
};
struct PackMe {
u64 uf : 8;
u64 total : 56;
};
static_assert(sizeof(Pack) == 8);
vector<u64> strategy(int N_, int r_, int i_, vector<u64> A, vector<u64> B) {
u64 N = N_, r = r_, i = i_;
auto uf = [&](u64 x) { return bit_cast<Pack>(B[x]).uf; };
auto set_uf = [&](u64 x, u64 root) {
const auto [_, j, w] = bit_cast<Pack>(B[x]);
B[x] = bit_cast<u64>(Pack{ root, j, w });
};
auto set_total = [&](u64& x, u64 total) {
const auto root = bit_cast<PackMe>(x).uf;
x = bit_cast<u64>(PackMe{ root, total });
};
u64 total = bit_cast<PackMe>(B[i]).total;
auto nearest = [&] {
u64 mn = -1, idx = i; // 無効値が idx = i でしか表現できない！
for (u64 j = 0; j < N; j++) {
if (uf(i) != uf(j) && mn > A[j]) {
mn = A[j];
idx = j;
}
}
return pair{mn, idx};
};
auto unite = [&](u64 u, u64 v) {
auto [x, y] = minmax({uf(u), uf(v)});
for (u64 j = 0; j < N; j++) if (uf(j) == y) {
set_uf(j, x);
}
};
// 辺を張るフェーズ
if (r == 0) {
// UF 初期化
for (u64 j = 0; j < N; j++) set_uf(j, j);
}
else if (r == 1) {
total = 0;
// Backup B
vector<Pack1> pack1(N);
for (u64 j = 0; j < N; j++) pack1[j] = bit_cast<Pack1>(B[j]);
// UF 初期化
for (u64 j = 0; j < N; j++) set_uf(j, j);
// 辺を繋ぐ
for (u64 u = 0; u < N; u++) {
const auto [v, v_2nd, w1] = pack1[u];
const auto [u_, u_2nd, w2] = pack1[v];
if (uf(u) == uf(v)) continue;
unite(u, v);
if (i == u) total += A[v]; // 1st min の重みは両端の小さい方が持つ
if (u_ == u) { // 双方向なら 2nd min を採用可能
auto e = min(tuple{w1, u, v_2nd}, tuple{w2, v, u_2nd});
const auto [w, u, v] = e;
if (uf(u) == uf(v)) continue;
unite(u, v);
if (i == 0) total += w; // 2nd min の重みは頂点 0 が持つ
}
}
} else if (r == 2 || r == 3) {
{ // 本来の B[i] を計算
auto [mn, idx] = nearest();
B[i] = bit_cast<u64>(Pack{ uf(i), idx, mn });
}
// 各連結成分から出る最小の辺を求め，接続
vector mn(N, pair<u64, u64>{-1, -1});
for (u64 u = 0; u < N; u++) {
const auto [_, v, w] = bit_cast<Pack>(B[u]);
chmin(mn[uf(u)], pair{w, v});
}
for (u64 u = 0; u < N; u++) {
if (uf(u) != u) continue;
const auto [w, v] = mn[u];
if (uf(u) != uf(v)) {
if (i == 0) total += w; // 以降の重みも頂点 0 が持つ
unite(u, v);
}
}
}
if (r == 5) {
assert(i == 0);
// Kruskal 法で答えを求める
vector<tuple<u64, u64, u64>> edges;
for (u64 u = 1; u < N; u++) {
const auto [_, v, w] = bit_cast<Pack>(B[u]);
edges.emplace_back(w, u, v);
}
ranges::sort(edges);
for (auto [w, u, v] : edges) {
if (uf(u) != uf(v)) {
total += w;
unite(u, v);
}
}
return {total};
}
// 送信フェーズ
r++;
if (r == 1) {
auto [w, idx] = nearest();
A[idx] = -1ULL;
auto [w2, idx2] = nearest();
vector<u64> res(N, bit_cast<u64>(Pack1 { idx, idx2, w2 }));
return res;
} else if (r == 2 || r == 3) {
auto [w, idx] = nearest();
vector<u64> res(N, bit_cast<u64>(Pack{ uf(i), idx, w }));
set_total(res[i], total);
return res;
} else if (r == 4) {
/*
i -> j に送るもの:
- i を含む連結成分の代表元 (8 bit)
- i - (j を含む連結成分) の最小重み (48 bit)
i -> 0 に送るもの:
- i を含む連結成分の代表元 (8 bit)
- total (56 bit)
*/
vector<u64> mn(N, -1ULL);
for (u64 j = 0; j < N; j++) {
const u64 u = uf(j);
if (mn[u] > A[j]) {
mn[u] = A[j];
}
}
vector<u64> ret(N);
for (u64 j = 0; j < N; j++) {
ret[j] = bit_cast<u64>(PackMe{ uf(i), mn[uf(j)] });
}
set_total(ret[0], total);
return ret;
} else if (r == 5) {
/*
i -> 0 に送るもの:
- i を含む連結成分の代表元 (8 bit)
- 各連結成分を 1 頂点に圧縮する．自身から出る辺の中で k 番目の辺の (重み, 行き先) (56 bit)
- k は自身の連結成分で何番目の頂点か
- 頂点 0 はこの送信を行わない (k は頂点 0 を無視して数える)
- k 番目の辺は存在しないかも (INF を送信する)
0 -> 0 に送るもの:
- i を含む連結成分の代表元 (8 bit)
- 現在の確定したコストの総和 (56 bit)
*/
if (i == 0) { // 頂点 0 は全ての連結成分の total を合計する
for (u64 j = 1; j < N; j++) total += bit_cast<PackMe>(B[j]).total;
return vector(N, bit_cast<u64>(PackMe{uf(0), total}));
}
// 自身の連結成分で何番目か？ (頂点 0 を無視)
u64 k = 0;
for (u64 j = 1; j < i; j++) k += uf(j) == uf(i);
// 各連結成分を圧縮
vector<u64> mn(N, -1ULL);
for (u64 j = 0; j < N; j++) {
const auto [_, w] = bit_cast<PackMe>(B[j]);
const u64 u = uf(j);
if (u != uf(i) && mn[u] > w) { // 自己辺は消す！
mn[u] = w;
}
}
// 辺をソートして k 番目の辺を得る
vector<pair<u64, u64>> edges(N);
for (u64 j = 0; j < N; j++) edges[j] = {mn[j], j};
ranges::sort(edges);
auto [w, u] = edges[k];
const u64 send = bit_cast<u64>(Pack{ uf(i), u, w });
return vector(N, send);
} else {
__builtin_unreachable();
}
}
