QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497471#7669. Maze ReductionMax_s_xaMAC ✓528ms112084kbC++144.0kb2024-07-29 09:33:042024-07-29 09:33:04

Judging History

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

  • [2024-07-29 09:33:04]
  • 评测
  • 测评结果:AC
  • 用时:528ms
  • 内存:112084kb
  • [2024-07-29 09:33:04]
  • 提交

answer

#include <iostream>
#include <vector>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 110, MAXM = 1e6 + 10;

int n;
vector <int> e[MAXN];
int id[MAXN][MAXN];
bool avl[MAXN]; int ans[MAXN];

int st[MAXM][3], top;
bool f[MAXN][MAXN][MAXN], vis[MAXN][MAXN][MAXN], inq[MAXN][MAXN][MAXN];
inline bool Solve(int u, int v, int d)
{
    if (vis[u][v][d]) return f[u][v][d];
    vis[u][v][d] = 1;
    top++, st[top][0] = u, st[top][1] = v, st[top][2] = d;
    inq[u][v][d] = 1;
    if (e[u].size() != e[v].size()) return f[u][v][d] = 0;
    bool flag = 1;
    for (int i = 0, j = d; i < e[u].size(); i++, (++j == e[u].size()) && (j = 0))
    {
        int t = max(e[e[v][j]].size(), e[e[u][i]].size());
        int dd = (id[e[v][j]][v] - id[e[u][i]][u] + t) % t;
        if (inq[e[u][i]][e[v][j]][dd]) continue;
        flag &= Solve(e[u][i], e[v][j], dd);
    }
    return f[u][v][d] = flag;
}

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n);
    for (int i = 1; i <= n; i++)
    {
        int m; Read(m);
        for (int j = 1, x; j <= m; j++) Read(x), e[i].push_back(x), id[i][x] = e[i].size() - 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            int t = max(e[i].size(), e[j].size());
            for (int k = 0; k < t; k++)
            {
                if (vis[i][j][k]) continue;
                bool cur = Solve(i, j, k);
                while (top) f[st[top][0]][st[top][1]][st[top][2]] = cur, inq[st[top][0]][st[top][1]][st[top][2]] = 0, top--;
            }
        }
    bool flag = 0;
    for (int i = 1; i <= n; i++)
        if (!avl[i])
        {
            int cnt = 0;
            ans[++cnt] = i;
            for (int j = i + 1; j <= n; j++)
            {
                int t = max(e[i].size(), e[j].size());
                if (t == 0) {ans[++cnt] = j; continue;}
                for (int k = 0; k < t; k++)
                    if (f[i][j][k]) {ans[++cnt] = j; break;}
            }
            if (cnt > 1)
            {
                for (int i = 1; i <= cnt; i++) cout << ans[i] << ' ', avl[ans[i]] = 1; cout << '\n';
                flag = 1;
            }
        }
    if (!flag) cout << "none\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5928kb

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: 7776kb

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: 1ms
memory: 5872kb

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: 7940kb

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: 1ms
memory: 5768kb

input:

1
0

output:

none

result:

ok single line: 'none'

Test #6:

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

input:

2
0
0

output:

1 2 

result:

ok single line: '1 2 '

Test #7:

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

input:

2
1 2
1 1

output:

1 2 

result:

ok single line: '1 2 '

Test #8:

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

input:

3
0
0
0

output:

1 2 3 

result:

ok single line: '1 2 3 '

Test #9:

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

input:

3
1 3
0
1 1

output:

1 3 

result:

ok single line: '1 3 '

Test #10:

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

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: 7700kb

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: 1ms
memory: 5728kb

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: 5696kb

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: 5672kb

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: 1ms
memory: 7756kb

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: 1ms
memory: 5960kb

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: 1ms
memory: 6400kb

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: 7712kb

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: 0ms
memory: 9036kb

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: 528ms
memory: 112084kb

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: 25ms
memory: 21004kb

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 ... 41 42 43 44 45 46 47 48 49 50 '

Test #22:

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

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: 1ms
memory: 5856kb

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: 1ms
memory: 5840kb

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: 1ms
memory: 5912kb

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: 3ms
memory: 9180kb

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: 9304kb

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 
6...

result:

ok 50 lines

Test #28:

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

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: 1ms
memory: 5884kb

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: 1ms
memory: 7804kb

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: 2ms
memory: 9292kb

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: 8ms
memory: 14304kb

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: 7080kb

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: 0ms
memory: 7740kb

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'