QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#462456#7302. Walk of Length 6alpha1022WA 1ms3996kbC++141.4kb2024-07-03 19:44:072024-07-03 19:44:08

Judging History

你现在查看的是最新测评结果

  • [2024-07-03 19:44:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3996kb
  • [2024-07-03 19:44:07]
  • 提交

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());
}

Details

Tip: Click on the bar to expand more detailed information

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'