QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369094#8215. Isomorphic Delight.5 ulp (Maxim Plyushkin, Egor Belousov, Maxim Inyutin)#AC ✓1476ms221800kbC++202.6kb2024-03-27 20:30:432024-03-27 20:30:44

Judging History

This is the latest submission verdict.

  • [2024-03-27 20:30:44]
  • Judged
  • Verdict: AC
  • Time: 1476ms
  • Memory: 221800kb
  • [2024-03-27 20:30:43]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 100;

uint64_t splitmix(uint64_t x) {
  x += 0x9e3779b97f4a7c15;
  (x ^= x >> 30) *= 0xbf58476d1ce4e5b9;
  (x ^= x >> 27) *= 0x94d049bb133111eb;
  return x ^ x >> 31;
}

int n;
vector<int> nei[N];
int sz[N];
vector<int> cent;

void findcent(int v, int p) {
  bool cent = 1;
  sz[v] = 1;
  for (auto u: nei[v]) if (u != p) {
    findcent(u, v);
    sz[v] += sz[u];
    cent &= sz[u] * 2 <= n;
  }
  if (cent && sz[v] * 2 >= n) ::cent.push_back(v);
}

uint64_t h[N];
bool ok;

uint64_t treehash(int v, int p) {
  if (!ok) return 0;
  uint64_t x = 0;
  for (auto u: nei[v]) if (u != p) x += treehash(u, v);
  for (auto u: nei[v]) if (u != p && ok)
  for (auto w: nei[v]) if (w != p) if (w == u) break; else ok &= h[w] != h[u];
  return h[v] = splitmix(x);
}

vector<vector<int>> rooted[N];
vector<vector<int>> unrooted[N];
set<uint64_t> urs;

void build(vector<int> p, int n, int m, int i, auto f) {
  if (!n) f(p);
  if (m > n) return;
  while (++i < rooted[m].size()) {
    auto t = rooted[m][i];
    for (auto& x: t) x += p.size() + 1;
    t.insert(t.begin(), 0);
    t.insert(t.begin(), p.begin(), p.end());
    build(t, n - m, m, i, f);
  }
  build(p, n, m + 1, -1, f);
}

constexpr int W = 1e6 + 1;

int can[W], last[W];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  rooted[1] = {{}};
  unrooted[1] = {{}};
  int nr = 1, nu = 1, su = 1;
  for (n = 2; nr < 1000000; nr += rooted[n].size(), nu += unrooted[n].size(), su += unrooted[n].size() * n, ++n)
  build({}, n - 1, 0, -1, [&](auto p) {
    for (int i = 0; i < n; ++i) nei[i].clear();
    for (int i = 1; i < n; ++i) nei[i].push_back(p[i - 1]), nei[p[i - 1]].push_back(i);
    rooted[n].push_back(p);
    ok = 1;
    cent.clear();
    findcent(0, 0);
    uint64_t h = treehash(cent[0], cent.back()), hh = h;
    if (ok && (cent.size() == 1 || h != (hh = treehash(cent[1], cent[0]))) && ok && urs.insert(h + hh).second) unrooted[n].push_back(p);
  });
  for (int w = 0; ++w < 22; )
  for (int i = W; i--; ) if (can[i] || !i)
  for (int c = 1, ww = i + w; ww < W && c <= unrooted[w].size() && can[ww] < can[i] + c; ++c, ww += w) can[ww] = can[i] + c, last[ww] = w;
  int n; cin >> n;
  if (n > 1 && n < 6) return cout << "NO", 0;
  cout << "YES\n";
  if (n == 6) {
    cout << "6\n1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n";
    return 0;
  }
  cout << n - can[n] << '\n';
  int d = 0;
  while (n) {
    auto p = unrooted[last[n]].back(); unrooted[last[n]].pop_back();
    for (int i = 0; i < p.size(); ++i) cout << d + i + 2 << ' ' << d + p[i] + 1 << '\n';
    d += last[n];
    n -= last[n];
  }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1387ms
memory: 220148kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 1374ms
memory: 220152kb

input:

6

output:

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

result:

ok Everything ok

Test #3:

score: 0
Accepted
time: 1336ms
memory: 218408kb

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 1358ms
memory: 220008kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 1412ms
memory: 221572kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 1476ms
memory: 218448kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 1391ms
memory: 219400kb

input:

7

output:

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

result:

ok Everything ok

Test #8:

score: 0
Accepted
time: 1371ms
memory: 221212kb

input:

8

output:

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

result:

ok Everything ok

Test #9:

score: 0
Accepted
time: 1382ms
memory: 217316kb

input:

9

output:

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

result:

ok Everything ok

Test #10:

score: 0
Accepted
time: 1423ms
memory: 220520kb

input:

10

output:

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

result:

ok Everything ok

Test #11:

score: 0
Accepted
time: 1362ms
memory: 217640kb

input:

11

output:

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

result:

ok Everything ok

Test #12:

score: 0
Accepted
time: 1381ms
memory: 217104kb

input:

12

output:

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

result:

ok Everything ok

Test #13:

score: 0
Accepted
time: 1347ms
memory: 221232kb

input:

13

output:

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

result:

ok Everything ok

Test #14:

score: 0
Accepted
time: 1379ms
memory: 218496kb

input:

14

output:

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

result:

ok Everything ok

Test #15:

score: 0
Accepted
time: 1332ms
memory: 217608kb

input:

15

output:

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

result:

ok Everything ok

Test #16:

score: 0
Accepted
time: 1396ms
memory: 217132kb

input:

16

output:

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

result:

ok Everything ok

Test #17:

score: 0
Accepted
time: 1344ms
memory: 219080kb

input:

17

output:

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

result:

ok Everything ok

Test #18:

score: 0
Accepted
time: 1393ms
memory: 220616kb

input:

18

output:

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

result:

ok Everything ok

Test #19:

score: 0
Accepted
time: 1388ms
memory: 218396kb

input:

19

output:

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

result:

ok Everything ok

Test #20:

score: 0
Accepted
time: 1362ms
memory: 220252kb

input:

598

output:

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

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 1382ms
memory: 219456kb

input:

245

output:

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

result:

ok Everything ok

Test #22:

score: 0
Accepted
time: 1333ms
memory: 217272kb

input:

793

output:

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

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 1376ms
memory: 217136kb

input:

133

output:

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

result:

ok Everything ok

Test #24:

score: 0
Accepted
time: 1458ms
memory: 218480kb

input:

681

output:

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

result:

ok Everything ok

Test #25:

score: 0
Accepted
time: 1357ms
memory: 218524kb

input:

922

output:

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

result:

ok Everything ok

Test #26:

score: 0
Accepted
time: 1355ms
memory: 218100kb

input:

876

output:

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

result:

ok Everything ok

Test #27:

score: 0
Accepted
time: 1367ms
memory: 221800kb

input:

7740

output:

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

result:

ok Everything ok

Test #28:

score: 0
Accepted
time: 1383ms
memory: 220240kb

input:

2460

output:

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

result:

ok Everything ok

Test #29:

score: 0
Accepted
time: 1367ms
memory: 220284kb

input:

7533

output:

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

result:

ok Everything ok

Test #30:

score: 0
Accepted
time: 1388ms
memory: 217608kb

input:

5957

output:

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

result:

ok Everything ok

Test #31:

score: 0
Accepted
time: 1396ms
memory: 219256kb

input:

92651

output:

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

result:

ok Everything ok

Test #32:

score: 0
Accepted
time: 1346ms
memory: 219984kb

input:

58779

output:

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

result:

ok Everything ok

Test #33:

score: 0
Accepted
time: 1382ms
memory: 218748kb

input:

12203

output:

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

result:

ok Everything ok

Test #34:

score: 0
Accepted
time: 1424ms
memory: 217348kb

input:

55627

output:

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

result:

ok Everything ok

Test #35:

score: 0
Accepted
time: 1417ms
memory: 216936kb

input:

99051

output:

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

result:

ok Everything ok

Test #36:

score: 0
Accepted
time: 1441ms
memory: 218304kb

input:

811713

output:

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

result:

ok Everything ok

Test #37:

score: 0
Accepted
time: 1432ms
memory: 220516kb

input:

544133

output:

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

result:

ok Everything ok

Test #38:

score: 0
Accepted
time: 1366ms
memory: 217364kb

input:

276553

output:

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

result:

ok Everything ok

Test #39:

score: 0
Accepted
time: 1428ms
memory: 220896kb

input:

736904

output:

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

result:

ok Everything ok

Test #40:

score: 0
Accepted
time: 1437ms
memory: 220164kb

input:

1000000

output:

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

result:

ok Everything ok

Extra Test:

score: 0
Extra Test Passed