QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641873#7669. Maze ReductionElegiaAC ✓10ms3852kbC++234.1kb2024-10-15 03:03:212024-10-15 03:03:22

Judging History

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

  • [2024-10-15 03:03:22]
  • 评测
  • 测评结果：AC
  • 用时：10ms
  • 内存：3852kb
查看
  • [2024-10-15 03:03:21]
  • 提交

answer

/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v)
    is >> x;
  return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int P = 998244353;

int norm(int x) { return x >= P ? (x - P) : x; }

void add(int &x, int y) { if ((x += y) >= P) x -= P; }

void sub(int &x, int y) { if ((x -= y) < 0) x += P; }

void exGcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}

int inv(int a) {
  int x, y;
  exGcd(a, P, x, y);
  return norm(x + P);
}

int mpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1)
      ret = ret * (ll) x % P;
    x = x * (ll) x % P;
    k >>= 1;
  }
  return ret;
}

const int Base = 114514, U = 1919810;
const int N = 110;

vector<int> g[N];
map<int, vector<int>> mp;
int h[N], t[N], tmp[N * 2];
vector<vector<int>> ans;

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int k;
    cin >> k;
    g[i].resize(k);
    cin >> g[i];
  }
  fill(h + 1, h + n + 1, 1);
  for (int rep = 0; rep <= n; ++rep) {
    memcpy(t, h, sizeof(h));
    for (int i = 1; i <= n; ++i)
      h[i] = h[i] * (ull) U % P;
    for (int i = 1; i <= n; ++i) {
      int k = g[i].size();
      for (int j = 0; j < k * 2; ++j)
        tmp[j + 1] = (tmp[j] * (ull) Base + t[g[i][j % k]]) % P;
      int p = mpow(Base, k);
      for (int j = 0; j < k; ++j)
        h[g[i][j]] = (h[g[i][j]] + tmp[j + k + 1] + (P - p) * (ull) tmp[j + 1]) % P;
    }
  }
  {
    memcpy(t, h, sizeof(h));
    for (int i = 1; i <= n; ++i)
      h[i] = h[i] * (ull) U % P;
    for (int i = 1; i <= n; ++i) {
      int k = g[i].size();
      for (int j = 0; j < k * 2; ++j)
        tmp[j + 1] = (tmp[j] * (ull) Base + t[g[i][j % k]]) % P;
      int p = mpow(Base, k);
      for (int j = 0; j < k; ++j)
        h[i] = (h[i] + tmp[j + k + 1] + (P - p) * (ull) tmp[j + 1]) % P;
    }
  }
  for (int i = 1; i <= n; ++i)
    mp[h[i]].push_back(i);
  for (const auto &pr : mp)
    if (pr.second.size() > 1)
      ans.push_back(pr.second);
  sort(ans.begin(), ans.end());
  if (ans.empty()) cout << "none\n";
  for (const auto &vec : ans)
    cout << vec << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

13
2 2 4
3 1 3 5
2 2 4
3 1 3 6
2 2 6
2 4 5
2 8 9
2 7 9
2 7 8
2 11 13
2 10 12
2 11 13
2 10 12

output:

2 4
5 6
7 8 9 10 11 12 13

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

6
3 3 4 5
0
1 1
1 1
2 1 6
1 5

output:

none

result:

ok single line: 'none'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

10
2 2 3
2 1 3
3 1 2 4
2 3 5
2 4 6
2 5 7
2 6 8
2 7 9
2 8 10
1 9

output:

none

result:

ok single line: 'none'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

10
2 2 3
2 1 3
3 1 2 4
2 3 5
2 4 6
2 5 7
2 6 8
3 7 9 10
2 8 10
2 8 9

output:

1 9
2 10
3 8
4 7
5 6

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

1
0

output:

none

result:

ok single line: 'none'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

2
0
0

output:

1 2

result:

ok single line: '1 2'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

2
1 2
1 1

output:

1 2

result:

ok single line: '1 2'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

3
0
0
0

output:

1 2 3

result:

ok single line: '1 2 3'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

3
1 3
0
1 1

output:

1 3

result:

ok single line: '1 3'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

3
2 2 3
2 3 1
2 2 1

output:

1 2 3

result:

ok single line: '1 2 3'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

4
1 2
2 1 3
2 2 4
1 3

output:

1 4
2 3

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

4
1 3
1 3
3 4 1 2
1 3

output:

1 2 4

result:

ok single line: '1 2 4'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

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

output:

1 2 3 4

result:

ok single line: '1 2 3 4'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

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

output:

3 4

result:

ok single line: '3 4'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

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

output:

1 2
3 4

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

15
2 2 3
3 1 4 5
3 1 6 7
3 2 8 9
3 2 10 11
3 3 12 13
3 3 14 15
1 4
1 4
1 5
1 5
1 6
1 6
1 7
1 7

output:

2 3
4 6
5 7
8 12
9 13
10 14
11 15

result:

ok 7 lines

Test #17:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

31
2 2 3
3 1 4 5
3 1 6 7
3 2 8 9
3 2 10 11
3 3 12 13
3 3 14 15
3 4 16 17
3 4 18 19
3 5 20 21
3 5 22 23
3 6 24 25
3 6 26 27
3 7 28 29
3 7 30 31
1 8
1 8
1 9
1 9
1 10
1 10
1 11
1 11
1 12
1 12
1 13
1 13
1 14
1 14
1 15
1 15

output:

2 3
4 6
5 7
8 12
9 13
10 14
11 15
16 24
17 25
18 26
19 27
20 28
21 29
22 30
23 31

result:

ok 15 lines

Test #18:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

63
2 2 3
3 1 4 5
3 1 6 7
3 2 8 9
3 2 10 11
3 3 12 13
3 3 14 15
3 4 16 17
3 4 18 19
3 5 20 21
3 5 22 23
3 6 24 25
3 6 26 27
3 7 28 29
3 7 30 31
3 8 32 33
3 8 34 35
3 9 36 37
3 9 38 39
3 10 40 41
3 10 42 43
3 11 44 45
3 11 46 47
3 12 48 49
3 12 50 51
3 13 52 53
3 13 54 55
3 14 56 57
3 14 58 59
3 15 60...

output:

2 3
4 6
5 7
8 12
9 13
10 14
11 15
16 24
17 25
18 26
19 27
20 28
21 29
22 30
23 31
32 48
33 49
34 50
35 51
36 52
37 53
38 54
39 55
40 56
41 57
42 58
43 59
44 60
45 61
46 62
47 63

result:

ok 31 lines

Test #19:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

91
8 3 19 31 43 87 30 78 13
4 80 18 24 81
8 87 78 13 1 43 19 30 31
12 54 8 59 67 79 22 91 41 57 83 17 25
11 16 64 58 61 84 12 7 32 45 85 15
7 76 63 68 82 71 69 33
11 32 16 84 85 5 45 15 12 58 64 61
12 41 79 54 4 91 67 83 22 59 57 17 25
10 49 34 86 77 53 60 89 23 72 50
9 29 75 62 37 44 51 35 47 21
2 ...

output:

1 3 13 19 30 31 43 78 87
2 18 24 80 81
4 8 17 22 25 41 54 57 59 67 79 83 91
5 7 12 15 16 32 45 58 61 64 84 85
6 33 63 68 69 71 76 82
9 23 34 49 50 53 60 72 77 86 89
10 21 29 35 37 44 47 51 62 75
11 27 65
14 39 48 55 56 70
20 26 28 38 46 66 74
36 90
40 42 52 73

result:

ok 12 lines

Test #20:

score: 0
Accepted
time: 10ms
memory: 3664kb

input:

100
99 31 20 72 66 27 54 67 85 78 11 59 44 77 38 89 47 13 15 33 4 23 86 22 28 32 80 43 39 51 75 25 88 37 69 3 12 50 84 30 76 56 57 29 46 19 63 87 55 18 96 16 53 26 10 62 34 8 36 99 93 91 73 81 83 97 7 52 60 94 68 58 6 79 65 14 61 40 71 42 70 24 90 2 64 98 92 49 82 74 21 41 48 45 95 9 35 17 5 100
99 ...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 91 92 93 94 95 96 97 98 99 100'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

50
49 18 36 12 40 6 29 31 24 27 11 7 39 28 33 44 42 23 16 3 41 46 38 13 30 45 37 14 25 15 34 47 8 49 26 48 20 43 35 32 10 19 22 21 4 5 17 9 2 50
49 8 6 38 29 32 37 4 7 11 18 22 41 45 48 17 21 14 43 40 24 9 34 35 47 44 33 1 28 5 46 20 27 12 39 50 36 15 10 49 31 25 13 3 30 23 19 16 26 42
49 26 25 6 24...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...0 41 42 43 44 45 46 47 48 49 50'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

8
3 2 3 5
3 6 4 1
3 1 4 7
3 2 8 3
3 7 6 1
3 8 2 5
3 3 8 5
3 7 4 6

output:

1 2 3 4 5 6 7 8

result:

ok single line: '1 2 3 4 5 6 7 8'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

8
4 2 4 3 5
3 6 4 1
3 1 4 7
4 1 2 8 3
3 7 6 1
3 8 2 5
3 3 8 5
3 7 4 6

output:

1 4
2 3
5 8
6 7

result:

ok 4 lines

Test #24:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

8
4 2 8 3 5
3 6 4 1
3 1 4 7
3 2 8 3
3 7 6 1
3 8 2 5
3 3 8 5
4 7 4 6 1

output:

1 8
2 6
3 7
4 5

result:

ok 4 lines

Test #25:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

8
4 2 3 5 4
3 6 4 1
3 1 4 7
4 2 8 3 1
3 7 6 1
3 8 2 5
3 3 8 5
3 7 4 6

output:

none

result:

ok single line: 'none'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

100
2 50 13
2 8 45
2 93 91
2 61 23
2 22 48
2 30 24
2 64 51
2 98 2
2 35 58
2 41 25
2 54 34
2 63 19
2 1 21
2 42 79
2 26 90
2 24 96
2 27 66
2 40 47
2 12 39
2 99 60
2 13 99
2 69 5
2 4 77
2 6 16
2 10 85
2 71 15
2 84 17
2 51 87
2 86 40
2 46 6
2 53 41
2 38 88
2 66 68
2 11 52
2 97 9
2 48 82
2 83 98
2 52 32
...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 91 92 93 94 95 96 97 98 99 100'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

100
3 50 2 13
3 8 45 1
2 93 91
2 61 23
2 22 48
2 30 24
2 64 51
2 98 2
2 35 58
2 41 25
2 54 34
2 63 19
2 1 21
2 42 79
2 26 90
2 24 96
2 27 66
2 40 47
2 12 39
2 99 60
2 13 99
2 69 5
2 4 77
2 6 16
2 10 85
2 71 15
2 84 17
2 51 87
2 86 40
2 46 6
2 53 41
2 38 88
2 66 68
2 11 52
2 97 9
2 48 82
2 83 98
2 52...

output:

1 2
3 40
4 7
5 90
6 96
8 13
9 17
10 52
11 85
12 94
14 79
15 48
16 24
18 93
19 59
20 83
21 98
22 65
23 64
25 34
26 36
27 58
28 80
29 91
30 75
31 32
33 97
35 66
37 99
38 41
39 55
42 44
43 46
45 50
47 57
49 70
51 61
53 88
54 62
56 89
60 77
63 78
67 74
68 76
69 72
71 82
73 84
81 87
86 92
95 100

result:

ok 50 lines

Test #28:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

25
3 2 6 7
3 3 1 8
3 4 2 9
3 5 3 10
3 6 4 11
3 1 5 12
1 1
2 2 13
1 3
2 4 14
1 5
2 6 15
1 8
1 10
1 12
3 19 17 20
3 21 16 18
3 17 19 22
3 16 23 18
2 16 24
1 17
2 18 25
1 19
1 20
1 22

output:

1 3 5 17 19
2 4 6 16 18
7 9 11 21 23
8 10 12 20 22
13 14 15 24 25

result:

ok 5 lines

Test #29:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

10
6 2 3 4 5 6 7
1 1
2 1 8
1 1
2 9 1
1 1
2 1 10
1 3
1 5
1 7

output:

2 4 6
3 5 7
8 9 10

result:

ok 3 lines

Test #30:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

10
6 2 4 3 5 6 7
1 1
2 1 8
1 1
2 9 1
1 1
2 1 10
1 3
1 5
1 7

output:

none

result:

ok single line: 'none'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

100
3 15 78 6
3 52 8 51
4 71 57 40 48
1 54
2 50 7
1 1
2 75 5
2 38 2
1 81
2 82 20
2 94 27
1 44
2 92 52
3 91 16 81
2 77 1
2 81 14
1 69
3 56 69 53
1 81
3 76 10 74
1 58
3 63 46 55
2 100 79
1 70
1 97
2 96 52
2 81 11
5 49 95 71 39 62
2 96 43
1 82
3 70 86 33
1 84
2 47 31
2 45 35
2 60 34
3 61 83 58
1 66
1 8...

output:

none

result:

ok single line: 'none'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

100
18 35 83 94 49 12 21 53 15 88 71 22 41 31 99 57 32 70 66
20 69 63 87 58 70 98 29 65 32 41 39 99 53 28 36 8 51 47 25 79
19 68 24 86 14 51 71 53 5 89 11 57 42 32 43 36 69 30 27 79
17 32 23 10 94 16 85 43 6 65 75 48 60 64 80 39 15 63
14 41 42 78 36 65 29 3 12 66 84 54 75 23 82
20 32 40 74 17 8 57 9...

output:

none

result:

ok single line: 'none'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

50
3 25 28 4
3 18 9 14
2 44 36
2 43 1
2 21 12
3 46 7 35
2 10 6
1 16
3 31 40 2
3 44 7 27
1 26
2 42 5
2 28 17
1 2
2 34 20
2 45 8
1 13
2 47 2
1 21
2 48 15
2 19 5
2 31 24
1 40
1 22
3 47 1 38
2 44 11
2 28 10
5 49 1 13 27 29
1 28
1 40
2 22 9
1 39
1 37
2 45 15
1 6
4 41 50 3 42
2 43 33
1 25
2 48 32
4 23 30 ...

output:

none

result:

ok single line: 'none'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

50
21 24 30 31 27 34 50 38 4 33 3 15 22 19 35 11 49 26 46 10 43 29
21 24 50 20 42 15 19 27 25 47 46 11 21 44 30 12 7 4 9 17 31 23
18 4 9 1 46 24 6 26 31 36 34 23 20 44 15 25 27 10 38
20 23 32 18 15 2 1 34 20 39 36 19 3 14 25 13 16 28 37 12 31
15 30 32 25 50 17 14 15 42 38 48 20 47 27 6 33
21 35 47 4...

output:

none

result:

ok single line: 'none'
English 繁體中文 简体中文

Server Time: 2024-12-02 22:56:23 | OpenSource Project