QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548463#8215. Isomorphic DelightHuTaoAC ✓407ms183676kbC++143.3kb2024-09-05 18:42:172024-09-05 18:42:17

Judging History

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

  • [2024-09-05 18:42:17]
  • 评测
  • 测评结果:AC
  • 用时:407ms
  • 内存:183676kb
  • [2024-09-05 18:42:17]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5, K = 23;

int n, m = 21;
vector<string> t1[K], t0[K];
int f[K][N], pre[K][N];
int q[N], hh, tt;
int pid;
vector<pair<int, int> > e;

inline bool CornerCases(int n)
{
    if(n == 1) return puts("YES\n0"), 1;
    if(n <= 5) return puts("NO"), 1;
    if(n == 6)
    {
        puts("YES");
        puts("6");
        puts("1 2");
        puts("1 3");
        puts("2 3");
        puts("1 4");
        puts("4 5");
        puts("2 6");
        return 1;
    }
    return 0;
}

inline void DFS(int n, string now, int siz, int lim, int pos, vector<string> &t)
{
    if((int)now.size() > n * 2) return ;
    if((int)now.size() == n * 2)
    {
        t.push_back("(" + now + ")");
        return ;
    }
    if(siz > lim) return ;
    DFS(n, now, siz + 1, lim, 0, t);
    for(int i = pos; i < (int)t1[siz].size(); i ++ )
        DFS(n, now + t1[siz][i], siz, lim, i + 1, t);
}
inline void SearchRootedTrees(int k)
{
    t1[1].push_back("()");
    for(int i = 2; i <= k; i ++ ) DFS(i - 1, "", 1, i - 1, 0, t1[i]);
}
inline void SearchUnrootedTrees(int k)
{
    t0[1].push_back("()");
    for(int i = 2; i <= k; i ++ )
    {
        DFS(i - 1, "", 1, (i - 1) / 2, 0, t0[i]);
        if(~i & 1)
        {
            for(int j = 0; j < (int)t1[i / 2].size(); j ++ )
                for(int k = j + 1; k < (int)t1[i / 2].size(); k ++ )
                {
                    t0[i].push_back(t1[i / 2][j]);
                    t0[i].back().pop_back();
                    t0[i].back() += t1[i / 2][k] + ")";
                }
        }
    }
    // for(int i = 1; i <= 8; i ++ )
    // {
    //     printf("#%d\n", i);
    //     for(string t : t0[i]) puts(t.c_str());
    // }
}

inline void DP(int n)
{
    memset(f[1], -0x3f, sizeof f[1]);
    f[1][0] = 0, f[1][1] = 1;
    for(int i = 2; i <= m; i ++ )
    {
        int c = t0[i].size();
        for(int j = 0; j < i; j ++ )
        {
            f[i][j] = f[i - 1][j], pre[i][j] = j;
            hh = tt = 0, q[0] = 0;
            for(int k = 1; k <= (n - j) / i; k ++ )
            {
                while(hh <= tt && q[hh] < k - c) hh ++ ;
                while(hh <= tt && f[i - 1][q[tt] * i + j] - q[tt] <= f[i - 1][k * i + j] - k) tt -- ;
                q[ ++ tt] = k;
                f[i][k * i + j] = f[i - 1][q[hh] * i + j] + k - q[hh];
                pre[i][k * i + j] = q[hh] * i + j;
            }
        }
    }
}

inline int GetTree(string &str, int l, int r)
{
    int u = ++ pid;
    for(int j = l + 1, k; j < r; j = k)
    {
        k = j + 1;
        int s = 1;
        while(s)
        {
            s += str[k] == '(' ? 1 : -1;
            k ++ ;
        }
        e.emplace_back(u, GetTree(str, j, k - 1));
    }
    return u;
}

int main()
{
    scanf("%d", &n);
    if(CornerCases(n)) return 0;
    SearchRootedTrees(m / 2);
    SearchUnrootedTrees(m);
    DP(n);
    for(int i = m, j = n; i >= 1; i -- )
    {
        int c = (j - pre[i][j]) / i;
        for(int k = 0; k < c; k ++ ) GetTree(t0[i][k], 0, i * 2 - 1);
        j = pre[i][j];
    }
    puts("YES");
    printf("%d\n", (int)e.size());
    for(pair<int, int> i : e) printf("%d %d\n", i.first, i.second);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

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

input:

6

output:

YES
6
1 2
1 3
2 3
1 4
4 5
2 6

result:

ok Everything ok

Test #3:

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

input:

4

output:

NO

result:

ok Everything ok

Test #4:

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

input:

2

output:

NO

result:

ok Everything ok

Test #5:

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

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 213ms
memory: 97420kb

input:

7

output:

YES
6
1 2
3 4
1 3
6 7
5 6
1 5

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 213ms
memory: 80840kb

input:

8

output:

YES
6
1 2
3 4
1 3
6 7
5 6
1 5

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 216ms
memory: 72624kb

input:

9

output:

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

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 222ms
memory: 97248kb

input:

10

output:

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

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 216ms
memory: 97220kb

input:

11

output:

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

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 216ms
memory: 97244kb

input:

12

output:

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

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 219ms
memory: 97152kb

input:

13

output:

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

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 218ms
memory: 97368kb

input:

14

output:

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

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 212ms
memory: 97160kb

input:

15

output:

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

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 220ms
memory: 97196kb

input:

16

output:

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

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 217ms
memory: 97204kb

input:

17

output:

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

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 214ms
memory: 97164kb

input:

18

output:

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

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 216ms
memory: 97180kb

input:

19

output:

YES
16
4 5
3 4
2 3
1 2
6 7
8 9
6 8
1 6
10 11
13 14
12 13
10 12
17 18
16 17
15 16
10 15

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 224ms
memory: 97280kb

input:

598

output:

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

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 216ms
memory: 97148kb

input:

245

output:

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

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 211ms
memory: 97216kb

input:

793

output:

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

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 212ms
memory: 97244kb

input:

133

output:

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

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 213ms
memory: 97148kb

input:

681

output:

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

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 214ms
memory: 99336kb

input:

922

output:

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

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 216ms
memory: 97360kb

input:

876

output:

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

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 218ms
memory: 99480kb

input:

7740

output:

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

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 218ms
memory: 97208kb

input:

2460

output:

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

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 207ms
memory: 97292kb

input:

7533

output:

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

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 209ms
memory: 99480kb

input:

5957

output:

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

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 227ms
memory: 115556kb

input:

92651

output:

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

result:

ok Everything ok

Test #32:

score: 0
Accepted
time: 221ms
memory: 108416kb

input:

58779

output:

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

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 211ms
memory: 99384kb

input:

12203

output:

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

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 225ms
memory: 106404kb

input:

55627

output:

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

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 234ms
memory: 115548kb

input:

99051

output:

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

result:

ok Everything ok

Test #36:

score: 0
Accepted
time: 339ms
memory: 176204kb

input:

811713

output:

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

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 299ms
memory: 160108kb

input:

544133

output:

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

result:

ok Everything ok

Test #38:

score: 0
Accepted
time: 277ms
memory: 145960kb

input:

276553

output:

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

result:

ok Everything ok

Test #39:

score: 0
Accepted
time: 346ms
memory: 175312kb

input:

736904

output:

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

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 407ms
memory: 183676kb

input:

1000000

output:

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

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed