Due to the success of TWICE, JYP Entertainment has earned countless money and emerged as the biggest entertainment firm by market capitalization. Therefore, the boss, JYP, has decided to create a new nation and has appointed you to provide a design diagram.
The new nation consists of $n$ cities and some roads between them. JYP has given some restrictions:
- To guarantee efficiency while avoiding chaos, for any $2$ different cities $A$ and $B$, there is exactly one road between them, and it is one-directional. There are no roads connecting a city to itself.
- The logo of rivaling companies should not appear in the plan, that is, there does not exist $4$ distinct cities $A$,$B$,$C$,$D$ , such that the following configuration occurs.
JYP has given criteria for your diagram. For two cities $A$,$B$, let $dis(A,B)$ be the smallest number of roads you have to go through to get from $A$ to $B$. If it is not possible to walk from $A$ to $B$, $dis(A,B) = 614n$. Then, the efficiency value is defined to be the sum of $dis(A,B)$ for all ordered pairs of distinct cities $(A,B)$.
Note that $dis(A,B)$ doesn’t have to be equal to $dis(B,A)$.
You have drawn a design diagram that satisfies JYP’s restrictions. Find the sum of $dis(A,B)$ over all ordered pairs of cities $(A,B)$ with $A\neq B$.
Note that the input is given in compressed form. But even though it is compressed, you’d better use fast input.Input
The first line contains a single integer $n$ ($4 \le n \le 8000$, $n \equiv 0 \pmod{4}$) — the number of cities.
A binary matrix is encrypted in the following format. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are $1011$, and if the number is $5$, then the corresponding elements are $0101$.
After you obtain the decrypted binary matrix, the $j$-th character of the $i$-th row is $1$ if the one-directional road between cities $i$ and $j$ is directed from $i$ to $j$, and $0$ otherwise. It is guaranteed that the graph satisfies the restrictions mentioned above.Output
Output one integer, representing the sum of $dis(A,B)$ over all ordered pairs of cities $(A,B)$ with $A\neq B$.Examplesinput
4 7 2 1 4
output
7380
input
8 7F 3F 1F 0C 06 03 11 18
output
88464
Note
The first example corresponds to the matrix:
$\begin{matrix} 0111 \\ 0010 \\ 0001 \\ 0100 \\ \end{matrix}$
Which corresponds to this graph:
$dis(1,2)=dis(1,3)=dis(1,4)=dis(2,3)=dis(3,4)=dis(4,2)=1$
$dis(2,4)=dis(4,3)=dis(3,2)=2$
$dis(2,1)=dis(3,1)=dis(4,1)=2456$
Therefore the answer for the diagram is $7380$.
Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<bool>> g(n, vector<bool>(n, false));
vector<int> din(n, 0);
vector<int> dout(n, 0);
for (int i = 0; i < n; i++) {
string foo;
cin >> foo;
for (int j = 0; j < (n >> 2); j++) {
char c = foo[j];
int d = (c <= '9' ? (int) (c - '0') : (int) (c - 'A' + 10));
for (int k = 0; k < 4; k++) {
if (d & (1 << (3 - k))) {
int x = (j << 2) | k;
g[i][x] = true;
dout[i] += 1;
din[x] += 1;
}
}
}
}
const long long none = 614LL * n;
long long ans = 0;
vector<bool> alive(n, true);
for (int rm = n; rm >= 1; rm--) {
bool found = false;
for (int i = 0; i < n; i++) {
if (alive[i] && dout[i] == rm - 1) {
alive[i] = false;
ans += (1 + none) * (rm - 1);
found = true;
break;
}
}
if (!found) {
vector<int> all;
for (int i = 0; i < n; i++) {
if (alive[i]) {
all.push_back(i);
}
}
debug(all);
assert((int) all.size() == rm);
vector<int> used(n, 0);
vector<int> seq(1, all[0]);
used[seq[0]] += 1;
vector<int> add;
vector<bool> in_seq(n, false);
in_seq[seq[0]] = true;
for (int it = 0; it < rm; it++) {
assert(it < (int) seq.size());
int v = seq[it];
in_seq[v] = false;
add.clear();
for (int j = 0; j < n; j++) {
if (v != j && !in_seq[j] && alive[j] && !g[v][j]) {
assert(used[j] < 2);
used[j] += 1;
add.push_back(j);
}
}
sort(add.begin(), add.end(), [&](int i, int j) {
return g[j][i];
});
for (int u : add) {
seq.push_back(u);
in_seq[u] = true;
}
}
seq.resize(rm);
reverse(seq.begin(), seq.end());
for (int i = 0; i < rm; i++) {
int cc = 0;
while (cc < rm - 1) {
ans += rm - 1 - cc;
cc += dout[seq[(i + cc) % rm]];
}
}
break;
}
}
cout << ans << '\n';
return 0;
}
