QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548511#8215. Isomorphic DelightHuTaoAC ✓229ms188648kbC++143.3kb2024-09-05 19:01:512024-09-05 19:01:52

Judging History

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

  • [2024-09-05 19:01:52]
  • 评测
  • 测评结果:AC
  • 用时:229ms
  • 内存:188648kb
  • [2024-09-05 19:01:51]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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

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, const int &ty, vector<string> &t)
{
    if((int)now.size() == n * 2)
    {
        t.push_back("(" + now + ")");
        return ;
    }
    if(siz > lim || (int)now.size() / 2 + siz > n) return ;
    DFS(n, now, siz + 1, lim, 0, ty, t);
    for(int i = pos; i < (int)t1[siz].size(); i ++ )
    {
        DFS(n, now + t1[siz][i], siz, lim, i + 1, ty, t);
        if(ty && (int)t.size() >= limit);
    }
}
inline void SearchRootedTrees(int k)
{
    t1[1].push_back("()");
    for(int i = 2; i <= k; i ++ ) DFS(i - 1, "", 1, i - 1, 0, 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, i == k, 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] + ")";
                }
            }
        }
    }
}

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

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

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

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

input:

4

output:

NO

result:

ok Everything ok

Test #4:

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

input:

2

output:

NO

result:

ok Everything ok

Test #5:

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

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 3ms
memory: 97236kb

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

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

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: 12ms
memory: 97276kb

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: 16ms
memory: 93116kb

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

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

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: 11ms
memory: 91084kb

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: 11ms
memory: 91304kb

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: 12ms
memory: 95404kb

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: 15ms
memory: 93216kb

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

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: 11ms
memory: 93076kb

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: 14ms
memory: 97460kb

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: 12ms
memory: 95188kb

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: 12ms
memory: 97284kb

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: 16ms
memory: 97164kb

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: 12ms
memory: 93080kb

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: 11ms
memory: 97280kb

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: 12ms
memory: 95188kb

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: 17ms
memory: 99460kb

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: 19ms
memory: 99288kb

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: 16ms
memory: 93272kb

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: 12ms
memory: 97168kb

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: 22ms
memory: 113624kb

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: 12ms
memory: 91628kb

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: 11ms
memory: 99688kb

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: 15ms
memory: 104536kb

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: 27ms
memory: 108996kb

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: 181ms
memory: 169916kb

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: 126ms
memory: 144760kb

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: 64ms
memory: 121496kb

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: 146ms
memory: 165820kb

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: 229ms
memory: 188648kb

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