QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#321408#8215. Isomorphic Delighthos_lyricAC ✓124ms109560kbC++145.4kb2024-02-04 17:13:442024-02-04 17:13:44

Judging History

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

  • [2024-02-04 17:13:44]
  • 评测
  • 测评结果:AC
  • 用时:124ms
  • 内存:109560kb
  • [2024-02-04 17:13:44]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// https://oeis.org/A000081
constexpr int UNLABELED_ROOTED[26] = {0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984, 2067174645};
// https://oeis.org/A000055
constexpr int UNLABELED_UNROOTED[29] = {0, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032};

namespace enu_tree {
constexpr int MAX_N = 21;

using Id = pair<int, int>;

// (largest subtree, remaining tree)
vector<pair<Id, Id>> T[MAX_N + 1];

inline int TLen(int n) {
  return T[n].size();
}

// tie-break (n/2) + (n/2)
inline bool isCentroid(int n, int x) {
  return (T[n][x].first <= T[n][x].second);
}

// |non-root subtree| <= limDn
void build(int limDn = MAX_N - 1) {
  for (int n = 0; n <= MAX_N; ++n) T[n].clear();
  T[1].emplace_back(Id(0, 0), Id(0, 0));
  for (int dn = 1; dn < MAX_N && dn <= limDn; ++dn) for (int dx = 0; dx < TLen(dn); ++dx) {
    for (int n = 1; n + dn <= MAX_N; ++n) for (int x = 0; x < TLen(n); ++x) {
      T[n + dn].emplace_back(Id(dn, dx), Id(n, x));
    }
  }
}

void getParDfs(int n, int x, int p, int &id, vector<int> &par) {
  const int u = id++;
  par[u] = p;
  for (int nn = n, xx = x; nn > 1; ) {
    const auto &t = T[nn][xx];
    getParDfs(t.first.first, t.first.second, u, id, par);
    nn = t.second.first;
    xx = t.second.second;
  }
}
vector<int> getPar(int n, int x) {
  assert(1 <= n); assert(n <= MAX_N);
  assert(0 <= x); assert(x < TLen(n));
  int id = 0;
  vector<int> par(n, -1);
  getParDfs(n, x, -1, id, par);
  return par;
}
vector<int> getPar(const Id &id) {
  return getPar(id.first, id.second);
}
}  // enu_tree

////////////////////////////////////////////////////////////////////////////////


vector<vector<int>> pars;

void exper() {
  using namespace enu_tree;
  build(MAX_N / 2);
  vector<int> dp[MAX_N + 1];
  dp[1] = {1};
  for (int n = 2; n <= MAX_N; ++n) {
    dp[n].assign(TLen(n), 1);
    for (int x = 0; x < TLen(n); ++x) {
      const auto a = T[n][x].first;
      const auto z = T[n][x].second;
      dp[n][x] &= dp[a.first][a.second];
      dp[n][x] &= dp[z.first][z.second];
      if (z.first > 1) {
        const auto b = T[z.first][z.second].first;
        if (a == b) {
          dp[n][x] = 0;
        }
      }
    }
  }
  int sum = 0;
  for (int n = 1; n <= MAX_N; ++n) {
    for (int x = 0; x < TLen(n); ++x) if (n == 1 || T[n][x].first < T[n][x].second) {
      if (dp[n][x]) {
        sum += n;
        // cerr << sum << " " << n << " " << x << " " << getPar(n, x) << endl;
        pars.push_back(getPar(n, x));
        if (sum >= 1'001'001) {
          cerr << n << ": " << sum << " " << pars.size() << endl;
          return;
        }
      }
    }
    cerr << n << ": " << sum << endl;
  }
}


int N;
vector<int> A, B;

void init() {
  A.clear();
  B.clear();
}
void ae(int u, int v) {
  A.push_back(u);
  B.push_back(v);
}

bool solve() {
  init();
  if (N == 1) {
    return true;
  } else if (N <= 5) {
    return false;
  } else if (N == 6) {
    ae(0, 1);
    ae(1, 2);
    ae(2, 0);
    ae(1, 3);
    ae(2, 4);
    ae(4, 5);
    return true;
  }
  int n = 0;
  for (int k = 0; n < N; ++k) {
    if (n + (int)pars[k].size() < N && n + (int)pars[k].size() + (int)pars[k + 1].size() > N) {
      assert(N - n >= 7);
      ae(n + 0, n + 1);
      ae(n + 0, n + 2); ae(n + 2, n + 3);
      int p = n + 0;
      for (int u = n + 4; u < N; ++u) {
        ae(p, u);
        p = u;
      }
      n = N;
      break;
    }
    const int dn = pars[k].size();
    for (int u = 1; u < dn; ++u) {
      ae(n + pars[k][u], n + u);
    }
    n += dn;
  }
  return true;
}

int main() {
  exper();
  
  for (; ~scanf("%d", &N); ) {
    const bool res = solve();
    if (res) {
      const int M = A.size();
      puts("YES");
      printf("%d\n", M);
      for (int i = 0; i < M; ++i) {
        printf("%d %d\n", A[i] + 1, B[i] + 1);
      }
    } else {
      puts("NO");
    }
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 59ms
memory: 109540kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 63ms
memory: 109516kb

input:

6

output:

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

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 55ms
memory: 109352kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 56ms
memory: 109460kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 72ms
memory: 109468kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 80ms
memory: 109460kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 59ms
memory: 109560kb

input:

7

output:

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

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 59ms
memory: 109264kb

input:

8

output:

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

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 56ms
memory: 109520kb

input:

9

output:

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

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 68ms
memory: 109404kb

input:

10

output:

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

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 84ms
memory: 109280kb

input:

11

output:

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

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 67ms
memory: 109224kb

input:

12

output:

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

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 72ms
memory: 109364kb

input:

13

output:

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

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 64ms
memory: 109416kb

input:

14

output:

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

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 39ms
memory: 109364kb

input:

15

output:

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

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 79ms
memory: 109388kb

input:

16

output:

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

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 55ms
memory: 109404kb

input:

17

output:

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

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 88ms
memory: 109308kb

input:

18

output:

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

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 63ms
memory: 109276kb

input:

19

output:

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

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 60ms
memory: 109392kb

input:

598

output:

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

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 63ms
memory: 109288kb

input:

245

output:

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

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 63ms
memory: 109468kb

input:

793

output:

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

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 63ms
memory: 109280kb

input:

133

output:

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

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 66ms
memory: 109392kb

input:

681

output:

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

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 67ms
memory: 109456kb

input:

922

output:

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

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 59ms
memory: 109392kb

input:

876

output:

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

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 66ms
memory: 109544kb

input:

7740

output:

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

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 68ms
memory: 109216kb

input:

2460

output:

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

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 84ms
memory: 109216kb

input:

7533

output:

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

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 71ms
memory: 109464kb

input:

5957

output:

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

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 55ms
memory: 109352kb

input:

92651

output:

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

result:

ok Everything ok

Test #32:

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

input:

58779

output:

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

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 59ms
memory: 109272kb

input:

12203

output:

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

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 52ms
memory: 109392kb

input:

55627

output:

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

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 62ms
memory: 109220kb

input:

99051

output:

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

result:

ok Everything ok

Test #36:

score: 0
Accepted
time: 124ms
memory: 109268kb

input:

811713

output:

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

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 103ms
memory: 109392kb

input:

544133

output:

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

result:

ok Everything ok

Test #38:

score: 0
Accepted
time: 88ms
memory: 109276kb

input:

276553

output:

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

result:

ok Everything ok

Test #39:

score: 0
Accepted
time: 120ms
memory: 109460kb

input:

736904

output:

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

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 116ms
memory: 109460kb

input:

1000000

output:

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

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed