QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317282 | #7302. Walk of Length 6 | ckiseki | Compile Error | / | / | C++20 | 4.4kb | 2024-01-28 19:26:38 | 2024-01-28 19:26:38 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC target("arch=skylake")
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
int64_t comb(int64_t a, int64_t b) {
if (a < b)
return 0;
b = min(b, a - b);
int64_t ans = 1;
for (int i = 0; i < b; ++i)
ans *= a - i;
for (int i = 1; i <= b; ++i)
ans /= i;
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
while (cin >> n) {
vector<string> a(n);
for (auto &ai : a)
cin >> ai;
vector<bitset<1000>> g(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = a[i][j] - '0';
}
}
vector<int64_t> d(n);
for (int i = 0; i < n; ++i)
d[i] = int(g[i].count());
vector<vector<int64_t>> intersect(n, vector<int64_t>(n, 0));
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
intersect[i][j] = (g[i] & g[j]).count();
auto Count1 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (not g[i][j])
continue;
ans += (d[i] - 1) * (d[j] - 1);
ans -= intersect[i][j];
}
}
return ans;
};
auto Count2 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
ans += comb(d[i], 2);
return ans;
};
auto Count3 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
ans += d[i];
assert(ans % 2 == 0);
return ans / 2;
};
auto Count4 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
ans += comb(d[i], 3);
return ans;
};
auto Count5 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (g[i][j])
ans += intersect[i][j];
assert(ans % 3 == 0);
return ans / 3;
};
auto Count7 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (not g[i][j])
continue;
ans += comb(intersect[i][j], 2);
}
}
return ans;
};
auto Count6 = [&] {
int64_t ans = 0;
vector<int64_t> count(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (not g[i][j])
continue;
count[i] += intersect[i][j];
count[j] += intersect[i][j];
}
}
for (int i = 0; i < n; ++i)
ans += comb(count[i] / 2, 2);
return ans - Count7() * 2;
};
auto Count8 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans += comb(intersect[i][j], 2);
assert(ans % 2 == 0);
return ans / 2;
};
auto Count9 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
if (d[i] < 3)
continue;
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
int64_t cur = comb(intersect[i][j], 2);
ans += cur * (d[i] - 2 - g[i][j]);
}
}
return ans;
};
cout << "Count1() = " << Count1() << '\n';
cout << "Count2() = " << Count2() << '\n';
cout << "Count3() = " << Count3() << '\n';
cout << "Count4() = " << Count4() << '\n';
cout << "Count5() = " << Count5() << '\n';
cout << "Count6() = " << Count6() << '\n';
cout << "Count7() = " << Count7() << '\n';
cout << "Count8() = " << Count8() << '\n';
cout << "Count9() = " << Count9() << '\n';
int64_t ans = 0;
ans += 6 * Count1();
ans += 12 * Count2();
ans += 2 * Count3();
ans += 12 * Count4();
ans += 24 * Count5();
ans += 20 * Count6();
ans += 32 * Count7();
ans += 48 * Count8();
ans += 12 * Count9();
cout << ans << '\n';
}
return 0;
}
Details
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148, from /usr/include/c++/13/ext/atomicity.h:35, from /usr/include/c++/13/bits/ios_base.h:39, from /usr/include/c++/13/streambuf:43, from /usr/include/c++/13/bits/streambuf_iterator.h:35, from /usr/include/c++/13/iterator:66, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54, from answer.code:3: /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 102 | __gthrw(pthread_once) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 103 | __gthrw(pthread_getspecific) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 104 | __gthrw(pthread_setspecific) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 106 | __gthrw(pthread_create) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 107 | __gthrw(pthread_join) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 108 | __gthrw(pthread_equal) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 109 | __gthrw(pthread_self) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 110 | __gthrw(pthread_detach) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 112 | __gthrw(pthread_cancel) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 114 | __gthrw(sched_yield) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 116 | __gthrw(pthread_mutex_lock) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 117 | __gthrw(pthread_mutex_trylock) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 119 | __gthrw(pthread_mutex_timedlock) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1:...