QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462456 | #7302. Walk of Length 6 | alpha1022 | WA | 1ms | 3996kb | C++14 | 1.4kb | 2024-07-03 19:44:07 | 2024-07-03 19:44:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3;
int n;
int deg[N + 5];
bitset<N + 5> e[N + 5];
int c[N + 5][N + 5];
ll s[9];
bool solve() {
if (!~scanf("%d", &n)) return 0;
for (int i = 1; i <= n; ++i) e[i].reset(), deg[i] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
int x; scanf("%1d", &x);
if (x) e[i].set(j), ++deg[i];
}
fill_n(s, 7, 0);
for (int i = 1; i <= n; ++i) {
s[3] += deg[i] * (deg[i] - 1) / 2,
s[5] += deg[i] * (deg[i] - 1) * (deg[i] - 2) / 6;
}
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j) {
c[i][j] = c[j][i] = (e[i] & e[j]).count();
if (e[i].test(j))
s[0] += c[i][j], ++s[2],
s[6] += c[i][j] * (c[i][j] - 1) / 2,
s[4] += (deg[i] - 1) * (deg[j] - 1);
s[1] += c[i][j] * (c[i][j] - 1) / 2,
s[7] += (ll)c[i][j] * (c[i][j] - 1) / 2 * (deg[i] + deg[j] - 4);
}
s[4] -= s[0], s[7] -= s[6] * 2, s[0] /= 3, s[1] /= 2;
for (int i = 1; i <= n; ++i) {
ll t = 0;
for (int j = 1; j <= n; ++j)
if (e[i].test(j))
t += c[i][j];
t /= 2, s[8] += t * (t - 1) / 2;
}
s[8] -= s[6] * 2;
printf("%lld\n", s[0] * 24 + s[1] * 48 + s[2] * 2 + s[3] * 12 + s[4] * 6 + s[5] * 12 + s[6] * 36 + s[7] * 12 + s[8] * 24);
return 1;
}
int main() {
while (solve());
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3752kb
input:
3 011 101 110 4 0101 1010 0101 1010 6 011111 101111 110111 111011 111101 111110
output:
66 128 14910
result:
ok 3 number(s): "66 128 14910"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3996kb
input:
1 0 2 01 10 3 011 100 100 3 011 101 110 4 0001 0001 0001 1110 4 0101 1001 0001 1110 4 0100 1001 0001 0110 4 0101 1011 0101 1110 4 0110 1001 1001 0110 4 0111 1011 1101 1110 5 01000 10111 01000 01000 01000 5 01111 10001 10000 10000 11000 5 01100 10110 11011 01100 00100 5 01111 10110 11010 11100 10000 ...
output:
0 2 16 66 54 116 36 298 128 732 128 202 408 890 128 220 842 1492 368 684 992 586 2778 1054 1212 1236 1060 1610 2272 1728 5468 2698 2784 3014 3544 3532 4254 3754 5648 4046 5058 8350 5296 5400 5660 6190 5362 6034 5586 5714 6756 6182 7410 8420 10114 13020 9776 9418 9546 10204 10950 10130 10034 10486 11...
result:
wrong answer 14th numbers differ - expected: '878', found: '890'