QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54267#860. We apologize for any inconvenienceckiseki#AC ✓3987ms13760kbC++201.6kb2022-10-07 18:24:332022-10-07 18:24:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 18:24:36]
  • 评测
  • 测评结果:AC
  • 用时:3987ms
  • 内存:13760kb
  • [2022-10-07 18:24:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(k);
    for (auto &ai : a) {
      int l;
      cin >> l;
      ai.resize(l);
      for (int &aij : ai) {
        cin >> aij;
        --aij;
      }
    }

    static constexpr int INF = 1 << 25;
    vector<vector<int>> d(n + k, vector<int>(n + k, INF));
    for (int i = 0; i < n + k; ++i)
      d[i][i] = 0;

    vector<int> o(n + k);
    for (int i = 0; i < n; ++i)
      o[i] = -1;

    int s;
    cin >> s;
    for (int i = 0; i < s; ++i) {
      int x;
      cin >> x;
      o[x - 1 + n] = s - i;
    }
    vector<int> u(n + k), v(n + k);
    iota(u.begin(), u.end(), 0);
    sort(u.begin(), u.end(), [&o](int i, int j) { return o[i] < o[j]; });
    for (int i = 0; i < n + k; ++i) {
      v[u[i]] = i;
    }
    for (int i = 0; i < k; ++i) {
      for (int j : a[i]) {
        int x = v[i + n], y = v[j];
        d[x][y] = 1, d[y][x] = 1;
      }
    }

    vector<int> ans(n + k);
    for (int z = 0; z < n + k; ++z) {
      for (int x = 0; x < n + k; ++x) {
        for (int y = 0; y < n + k; ++y) {
          d[x][y] = min(d[x][y], d[x][z] + d[z][y]);
        }
      }

      for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
          if (d[x][y] == INF)
            continue;
          ans[z] = max(ans[z], d[x][y]);
        }
      }
    }
    for (int i = 0; i <= s; ++i)
      cout << ans[n + k - 1 - i] / 2 - 1 << '\n';
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3720kb

input:

1
5 4
3 1 3 5
2 1 4
2 2 3
2 2 4
3
1
4
3

output:

1
2
0
0

result:

ok 4 number(s): "1 2 0 0"

Test #2:

score: 0
Accepted
time: 86ms
memory: 4104kb

input:

35
20 20
2 2 13
2 2 9
7 10 3 9 15 5 11 4
9 16 19 15 4 17 18 5 3 8
8 12 20 16 11 18 9 6 4
12 4 18 15 17 6 16 19 14 7 5 20 9
3 8 14 4
5 14 7 9 17 5
3 17 11 20
15 19 11 16 5 8 13 15 20 18 9 10 14 7 4 3
13 19 10 17 6 8 15 9 4 12 20 7 14 16
5 4 12 11 6 18
14 20 17 18 4 8 15 11 16 14 6 5 13 19 3
8 3 10 8 ...

output:

1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
1
1
0
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
1
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
2
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
0
...

result:

ok 893 numbers

Test #3:

score: 0
Accepted
time: 3987ms
memory: 13008kb

input:

2
750 750
2 47 500
2 51 145
2 22 531
2 22 354
2 22 727
2 25 700
2 7 159
2 42 356
2 57 727
2 28 237
2 57 714
2 68 511
2 29 81
2 65 318
2 43 91
2 65 488
2 68 549
2 16 310
2 30 618
2 6 105
2 7 468
2 34 253
2 51 155
2 21 205
2 22 470
2 36 642
2 17 649
2 66 229
2 10 409
2 65 105
2 21 395
2 51 552
2 25 55...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 3356ms
memory: 12144kb

input:

4
750 750
2 511 512
2 649 650
2 154 155
2 128 129
2 344 345
2 453 454
2 613 614
2 10 11
2 491 492
2 356 357
2 299 300
2 294 295
2 699 700
2 441 442
2 13 14
2 78 79
2 583 584
2 430 431
2 342 343
2 63 64
2 547 548
2 100 101
2 584 585
2 14 15
2 33 34
2 619 620
2 2 3
2 392 393
2 383 384
2 631 632
2 614 ...

output:

748
695
444
444
444
444
326
326
326
257
257
257
162
162
162
152
152
152
152
152
93
93
93
93
93
93
93
93
93
93
93
93
93
72
72
72
72
72
72
62
62
62
62
62
62
62
62
62
62
62
62
62
62
62
49
49
48
48
48
48
48
48
48
48
48
48
48
48
48
48
42
37
37
37
37
37
37
37
37
37
37
37
37
37
37
37
37
33
26
26
26
26
26
2...

result:

ok 997 numbers

Test #5:

score: 0
Accepted
time: 3781ms
memory: 13760kb

input:

2
750 750
540 514 18 412 670 208 26 633 215 378 588 530 101 563 276 247 697 596 328 83 129 494 13 298 582 269 222 649 57 14 365 325 419 679 579 747 583 97 571 744 632 61 622 681 67 127 624 524 399 216 589 275 644 271 442 447 444 460 184 118 542 290 746 613 704 25 353 477 364 715 292 294 224 201 512 ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 1996ms
memory: 7500kb

input:

2
498 498
164 139 208 482 253 14 37 20 228 198 467 39 174 48 288 353 155 190 246 119 455 76 149 167 128 375 183 415 373 212 425 36 161 304 348 310 204 497 231 399 490 324 211 475 340 309 24 58 151 166 471 443 321 286 67 473 251 219 383 277 176 142 171 82 86 136 427 235 278 498 343 23 391 85 60 110 2...

output:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 996 numbers

Test #7:

score: 0
Accepted
time: 2121ms
memory: 7784kb

input:

2
500 500
2 1 2
2 2 1
2 3 4
2 4 3
2 5 6
2 6 5
2 7 8
2 8 7
2 9 10
2 10 9
2 11 12
2 12 11
2 13 14
2 14 13
2 15 16
2 16 15
2 17 18
2 18 17
2 19 20
2 20 19
2 21 22
2 22 21
2 23 24
2 24 23
2 25 26
2 26 25
2 27 28
2 28 27
2 29 30
2 30 29
2 31 32
2 32 31
2 33 34
2 34 33
2 35 36
2 36 35
2 37 38
2 38 37
2 39...

output:

1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers