bigW and GirrySnake777 will AK ioi!↵
↵
↵
↵
~~~~~↵
#include "multi.h"↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
namespace {↵
using ull = unsigned long long;↵
↵
struct info {↵
int idx1, idx2;↵
ull weight;↵
};↵
↵
const ull c1 = 0xFF, c2 = 0xFFFFFFFFFFFF, c3 = 0xFFFFFFFFFFFFFF;↵
constexpr ull pack(info i, int type) { return ((ull)(i.idx1) << 56) + type * ((ull)(i.idx2) << 48) + i.weight; }↵
constexpr info unpack(ull i, int type) { return info{ (int)(i >> 56), (int)((i >> 48) & c1), i & (type ? c2 : c3) }; }↵
↵
int N, r, i;↵
ull total;↵
vector<ull> A, B, C;↵
vector<info> infos, auxinfo;↵
vector<int> p, ss;↵
vector<int> leaders;↵
vector<ull> edgeweights;↵
vector<pair<int, int>> bedges;↵
↵
int fin(int n) {↵
if (p[n] == n) return n;↵
return p[n] = fin(p[n]);↵
}↵
↵
void join(int a, int b, bool add = 1) {↵
int oa = a, ob = b;↵
a = fin(a), b = fin(b);↵
if (a == b) return;↵
if (a < b) swap(a, b);↵
if (add && i == min(oa, ob)) total += A[max(oa, ob)];↵
ss[b] += ss[a];↵
p[a] = b;↵
}↵
↵
void reset() {↵
A.clear(); B.clear(); C.clear();↵
infos.clear(); auxinfo.clear(); p.clear(); ss.clear();↵
leaders.clear(); edgeweights.clear(); bedges.clear();↵
}↵
}↵
↵
vector<ull> strategy(int _N, int _r, int _i, vector<ull> _A, vector<ull> _B) {↵
reset();↵
N = _N, r = _r, i = _i, A = _A, B = _B;↵
if (N == 2) return { A[!i] };↵
C.resize(N, 0);↵
ss.resize(N, 1);↵
for (int j = 0; j < N; j++) p.push_back(j);↵
for (int j = 0; j < N; j++) infos.push_back(unpack(B[j], !((i == j && r != 4 && r != 1) || (i == 0 && r == 4))));↵
auxinfo.resize(N, { -1, 0, c2 });↵
total = (r == 1 ? 0ull : infos[i].weight);↵
info crnt{ 0, 0, c2 }; ull minw = c2;↵
for (int j = 0; j < N; j++) {↵
if (i == j) continue;↵
if (A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;↵
if (crnt.weight < minw) {↵
swap(minw, crnt.weight);↵
swap(crnt.idx1, crnt.idx2);↵
}↵
}↵
if (r == 1) {↵
for (int j = 0; j < N; j++) join(j, infos[j].idx1);↵
for (int j = 0; j < N; j++) {↵
if (ss[fin(j)] == 2) {↵
if (infos[j].weight < infos[infos[j].idx1].weight) join(j, infos[j].idx2);↵
else join(infos[j].idx1, infos[infos[j].idx1].idx2);↵
}↵
}↵
}↵
else if (r <= 5) for (int j = 0; j < N; j++) p[j] = infos[j].idx1;↵
if (r == 2 || r == 3) {↵
crnt.weight = c2;↵
for (int j = 0; j < N; j++) if (infos[i].idx1 != fin(j) && A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;↵
infos[i] = crnt;↵
for (int j = 0; j < N; j++) if (infos[j].weight < auxinfo[fin(j)].weight) auxinfo[fin(j)].weight = infos[j].weight, auxinfo[fin(j)].idx2 = infos[j].idx2, auxinfo[fin(j)].idx1 = j;↵
for (int j = 0; j < N; j++) if (auxinfo[fin(j)].idx1 != -1) join(auxinfo[fin(j)].idx1, auxinfo[fin(j)].idx2);↵
}↵
else if (r == 4) {↵
if (i == 0) for (int j = 1; j < N; j++) total += infos[j].weight;↵
}↵
if (r == 3 || r == 4 || (r == 5 && i == 0)) {↵
for (int j = 0; j < N; j++) if (p[j] == j) leaders.push_back(j);↵
for (int j = 0; j < leaders.size(); j++) for (int k = 0; k < j; k++) bedges.push_back({ j, k });↵
edgeweights.resize(leaders.size(), c2);↵
}↵
if (r == 0) for (int j = 0; j < N; j++) C[j] = pack(crnt, 1);↵
else if (r == 1 || r == 2) {↵
crnt.weight = c2, crnt.idx1 = fin(i);↵
for (int j = 0; j < N; j++) if (crnt.idx1 != fin(j) && A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;↵
for (int j = 0; j < N; j++) C[j] = pack(crnt, 1);↵
C[i] = pack({ crnt.idx1, 0, total }, 0);↵
}↵
else if (r == 3) {↵
for (int j = 0; j < leaders.size(); j++) for (int k = 0; k < N; k++) if (fin(k) == leaders[j] && A[k] < edgeweights[j]) edgeweights[j] = A[k];↵
for (int j = 1; j <= bedges.size(); j++) C[j] = pack({ fin(i), 0, edgeweights[bedges[j - 1].first] }, 1);↵
for (int j = bedges.size() + 1; j < N; j++) C[j] = pack({ fin(i), 0, 0 }, 1);↵
C[0] = pack({ fin(i), 0, total }, 0);↵
}↵
else if (r == 4) {↵
if (i == 0) C[0] = pack({ fin(i), 0, total }, 0);↵
else if (i <= bedges.size()) {↵
crnt.weight = c2, crnt.idx1 = fin(i);↵
for (int j = 0; j < N; j++) if (infos[j].idx1 == leaders[bedges[i - 1].second] && infos[j].weight < crnt.weight) crnt.weight = infos[j].weight;↵
C[0] = pack(crnt, 1);↵
}↵
else C[0] = pack({ fin(i), 0, 0 }, 1);↵
}↵
else if (r == 5) {↵
if (i == 0) {↵
vector<pair<ull, pair<int, int>>> edges;↵
for (int j = 1; j <= bedges.size(); j++) edges.push_back({ infos[j].weight, bedges[j - 1] });↵
sort(edges.begin(), edges.end());↵
p.clear();↵
for (int j = 0; j < leaders.size(); j++) p.push_back(j);↵
for (int j = 0; j < bedges.size(); j++) {↵
if (fin(edges[j].second.first) == fin(edges[j].second.second)) continue;↵
join(edges[j].second.first, edges[j].second.second, 0);↵
total += edges[j].first;↵
}↵
return { total };↵
}↵
}↵
return C;↵
}↵
~~~~~↵
↵
↵
↵
↵
~~~~~↵
#include "multi.h"↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
namespace {↵
using ull = unsigned long long;↵
↵
struct info {↵
int idx1, idx2;↵
ull weight;↵
};↵
↵
const ull c1 = 0xFF, c2 = 0xFFFFFFFFFFFF, c3 = 0xFFFFFFFFFFFFFF;↵
constexpr ull pack(info i, int type) { return ((ull)(i.idx1) << 56) + type * ((ull)(i.idx2) << 48) + i.weight; }↵
constexpr info unpack(ull i, int type) { return info{ (int)(i >> 56), (int)((i >> 48) & c1), i & (type ? c2 : c3) }; }↵
↵
int N, r, i;↵
ull total;↵
vector<ull> A, B, C;↵
vector<info> infos, auxinfo;↵
vector<int> p, ss;↵
vector<int> leaders;↵
vector<ull> edgeweights;↵
vector<pair<int, int>> bedges;↵
↵
int fin(int n) {↵
if (p[n] == n) return n;↵
return p[n] = fin(p[n]);↵
}↵
↵
void join(int a, int b, bool add = 1) {↵
int oa = a, ob = b;↵
a = fin(a), b = fin(b);↵
if (a == b) return;↵
if (a < b) swap(a, b);↵
if (add && i == min(oa, ob)) total += A[max(oa, ob)];↵
ss[b] += ss[a];↵
p[a] = b;↵
}↵
↵
void reset() {↵
A.clear(); B.clear(); C.clear();↵
infos.clear(); auxinfo.clear(); p.clear(); ss.clear();↵
leaders.clear(); edgeweights.clear(); bedges.clear();↵
}↵
}↵
↵
vector<ull> strategy(int _N, int _r, int _i, vector<ull> _A, vector<ull> _B) {↵
reset();↵
N = _N, r = _r, i = _i, A = _A, B = _B;↵
if (N == 2) return { A[!i] };↵
C.resize(N, 0);↵
ss.resize(N, 1);↵
for (int j = 0; j < N; j++) p.push_back(j);↵
for (int j = 0; j < N; j++) infos.push_back(unpack(B[j], !((i == j && r != 4 && r != 1) || (i == 0 && r == 4))));↵
auxinfo.resize(N, { -1, 0, c2 });↵
total = (r == 1 ? 0ull : infos[i].weight);↵
info crnt{ 0, 0, c2 }; ull minw = c2;↵
for (int j = 0; j < N; j++) {↵
if (i == j) continue;↵
if (A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;↵
if (crnt.weight < minw) {↵
swap(minw, crnt.weight);↵
swap(crnt.idx1, crnt.idx2);↵
}↵
}↵
if (r == 1) {↵
for (int j = 0; j < N; j++) join(j, infos[j].idx1);↵
for (int j = 0; j < N; j++) {↵
if (ss[fin(j)] == 2) {↵
if (infos[j].weight < infos[infos[j].idx1].weight) join(j, infos[j].idx2);↵
else join(infos[j].idx1, infos[infos[j].idx1].idx2);↵
}↵
}↵
}↵
else if (r <= 5) for (int j = 0; j < N; j++) p[j] = infos[j].idx1;↵
if (r == 2 || r == 3) {↵
crnt.weight = c2;↵
for (int j = 0; j < N; j++) if (infos[i].idx1 != fin(j) && A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;↵
infos[i] = crnt;↵
for (int j = 0; j < N; j++) if (infos[j].weight < auxinfo[fin(j)].weight) auxinfo[fin(j)].weight = infos[j].weight, auxinfo[fin(j)].idx2 = infos[j].idx2, auxinfo[fin(j)].idx1 = j;↵
for (int j = 0; j < N; j++) if (auxinfo[fin(j)].idx1 != -1) join(auxinfo[fin(j)].idx1, auxinfo[fin(j)].idx2);↵
}↵
else if (r == 4) {↵
if (i == 0) for (int j = 1; j < N; j++) total += infos[j].weight;↵
}↵
if (r == 3 || r == 4 || (r == 5 && i == 0)) {↵
for (int j = 0; j < N; j++) if (p[j] == j) leaders.push_back(j);↵
for (int j = 0; j < leaders.size(); j++) for (int k = 0; k < j; k++) bedges.push_back({ j, k });↵
edgeweights.resize(leaders.size(), c2);↵
}↵
if (r == 0) for (int j = 0; j < N; j++) C[j] = pack(crnt, 1);↵
else if (r == 1 || r == 2) {↵
crnt.weight = c2, crnt.idx1 = fin(i);↵
for (int j = 0; j < N; j++) if (crnt.idx1 != fin(j) && A[j] < crnt.weight) crnt.weight = A[j], crnt.idx2 = j;↵
for (int j = 0; j < N; j++) C[j] = pack(crnt, 1);↵
C[i] = pack({ crnt.idx1, 0, total }, 0);↵
}↵
else if (r == 3) {↵
for (int j = 0; j < leaders.size(); j++) for (int k = 0; k < N; k++) if (fin(k) == leaders[j] && A[k] < edgeweights[j]) edgeweights[j] = A[k];↵
for (int j = 1; j <= bedges.size(); j++) C[j] = pack({ fin(i), 0, edgeweights[bedges[j - 1].first] }, 1);↵
for (int j = bedges.size() + 1; j < N; j++) C[j] = pack({ fin(i), 0, 0 }, 1);↵
C[0] = pack({ fin(i), 0, total }, 0);↵
}↵
else if (r == 4) {↵
if (i == 0) C[0] = pack({ fin(i), 0, total }, 0);↵
else if (i <= bedges.size()) {↵
crnt.weight = c2, crnt.idx1 = fin(i);↵
for (int j = 0; j < N; j++) if (infos[j].idx1 == leaders[bedges[i - 1].second] && infos[j].weight < crnt.weight) crnt.weight = infos[j].weight;↵
C[0] = pack(crnt, 1);↵
}↵
else C[0] = pack({ fin(i), 0, 0 }, 1);↵
}↵
else if (r == 5) {↵
if (i == 0) {↵
vector<pair<ull, pair<int, int>>> edges;↵
for (int j = 1; j <= bedges.size(); j++) edges.push_back({ infos[j].weight, bedges[j - 1] });↵
sort(edges.begin(), edges.end());↵
p.clear();↵
for (int j = 0; j < leaders.size(); j++) p.push_back(j);↵
for (int j = 0; j < bedges.size(); j++) {↵
if (fin(edges[j].second.first) == fin(edges[j].second.second)) continue;↵
join(edges[j].second.first, edges[j].second.second, 0);↵
total += edges[j].first;↵
}↵
return { total };↵
}↵
}↵
return C;↵
}↵
~~~~~↵
↵
