QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359467#8215. Isomorphic Delightinstallb#WA 61ms12956kbC++235.4kb2024-03-20 18:07:232024-03-20 18:07:23

Judging History

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

  • [2024-03-20 18:07:23]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:12956kb
  • [2024-03-20 18:07:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SZ = 21;

struct tree{
    int n,id;
    vector <pair <int,int> > E;
}; int tot = 0;

int P[2] = {998244353,1000000007};
int h[2][SZ + 5];
vector <int> G[SZ + 5];
unsigned int xorshift(unsigned int x,int id){
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x %= P[id];
    return x;
}
int fa[SZ + 5];
void dfs_hash(int u,int f){
    h[0][u] = h[1][u] = 1;
    fa[u] = f;
    for(int v : G[u]){
        if(v == f) continue;
        dfs_hash(v,u);
        for(int id = 0;id < 2;id ++)
            h[id][u] = (h[id][u] + xorshift(h[id][v],id)) % P[id];
    }
}

void settr(tree x){
    for(int i = 1;i <= x.n;i ++) G[i].clear();
    for(auto [x,y] : x.E){
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

vector <tree> tr[SZ + 5];
tree son[SZ + 5];

void dfs_rooted(int dep,int sz){
    if(sz == 0){
        tree cur;
        cur.n = 1;
        for(int i = 1;i < dep;i ++){
            cur.E.push_back({1,cur.n + 1});
            for(auto [x,y] : son[i].E){
                cur.E.push_back({cur.n + x,cur.n + y});
            }
            cur.n += son[i].n;
        }
        settr(cur);
        cur.id = ++ tot;
        tr[cur.n].push_back(cur);
        return;
    }
    for(int i = 1;i <= sz;i ++){
        for(tree x : tr[i]){
            if(x.id <= son[dep - 1].id) continue;
            son[dep] = x;
            dfs_rooted(dep + 1,sz - i);
        }
    }
}

vector <tree> ans_tree;

int siz[SZ + 5],mxs[SZ + 5];
void dfs_sz(int u,int f){
    siz[u] = 1;
    mxs[u] = 0;
    fa[u] = f;
    for(int v : G[u]){
        if(v == f) continue;
        dfs_sz(v,u);
        siz[u] += siz[v];
        mxs[u] = max(mxs[u],siz[v]);
    }
}
pair <int,int> calc_cen(int n){
    dfs_sz(1,0);
    vector <int> ret; int mi = n + 1;
    for(int i = 1;i <= n;i ++) mi = min(mi,max(mxs[i],n - siz[i]));
    for(int i = 1;i <= n;i ++) if(max(mxs[i],n - siz[i]) == mi) ret.push_back(i);
    if(ret.size() == 1) return {ret[0],-1};
    return {ret[0],ret[1]};
}

int num = 0;
void dfs(int dep,int sz,int szlim){
    if(num > 1000000) return;
    if(sz == 0){
        tree cur;
        cur.n = 1;
        for(int i = 1;i < dep;i ++){
            cur.E.push_back({1,cur.n + 1});
            for(auto [x,y] : son[i].E){
                cur.E.push_back({cur.n + x,cur.n + y});
            }
            cur.n += son[i].n;
        }
        settr(cur);

        auto [u,v] = calc_cen(cur.n);
        if(v != -1){
            pair <int,int> v1,v2;
            dfs_hash(u,0);
            v1 = {h[0][v],h[1][v]};
            dfs_hash(v,0);
            v2 = {h[0][u],h[1][u]};
            if(v1 == v2) return;
        }
        cur.id = ++ tot;
        ans_tree.push_back(cur);

        num += cur.n;

        return;
    }
    for(int i = 1;i <= min(sz,szlim / 2);i ++){
        for(int j = 1;j < tr[i].size();j ++) assert(tr[i][j].id > tr[i][j - 1].id);
        for(tree x : tr[i]){
            if(x.id <= son[dep - 1].id) continue;
            son[dep] = x;
            dfs(dep + 1,sz - i,szlim);
        }
    }
}

void init(){
    tree now;
    now.n = 1; now.id = ++ tot;
    tr[1].push_back(now);
    ans_tree.push_back(now);
    for(int cur_sz = 2;cur_sz <= (SZ / 2);cur_sz ++) dfs_rooted(1,cur_sz - 1);
    for(int cur_sz = 7;cur_sz <= SZ;cur_sz ++){
        dfs(1,cur_sz - 1,cur_sz);
    }
    sort(ans_tree.begin(),ans_tree.end(),[&](tree x,tree y){ return x.n < y.n; });
}

void solve(){
    int n; cin >> n;
    vector <pair <int,int> > vec;
    if(n == 1){
        cout << "YES\n0\n";
    }
    else if(n >= 2 && n <= 5){
        cout << "NO\n";
    }
    else if(n == 6){
        cout << "YES\n";
        cout << "6" << '\n';
        cout << "1 2" << '\n';
        cout << "2 3" << '\n';
        cout << "1 3" << '\n';
        cout << "3 4" << '\n';
        cout << "2 5" << '\n';
        cout << "5 6" << '\n';
    }
    else if(n == 7){
        cout << "YES\n";
        cout << "6" << '\n';
        cout << "1 2" << '\n';
        cout << "1 3" << '\n';
        cout << "3 4" << '\n';
        cout << "1 5" << '\n';
        cout << "5 6" << '\n';
        cout << "6 7" << '\n';
    }
    else{
        int now = 0;
        for(int i = 0;i < ans_tree.size();i ++){
            if(n - ans_tree[i].n < ans_tree[i + 1].n){
                // this is the last tree
                settr(ans_tree[i]);
                dfs_sz(1,0);
                int u = 1;
                while(1){
                    int id = -1;
                    for(int v : G[u]){
                        if(v == fa[u]) continue;
                        if(id == -1 || siz[v] > siz[id]) id = v;
                    }
                    if(id == -1) break;
                    u = id;
                }
                while(n > ans_tree[i].n){
                    ans_tree[i].E.push_back({u,++ ans_tree[i].n});
                    u = ans_tree[i].n;
                }
            }
            for(auto [u,v] : ans_tree[i].E) vec.push_back({u + now,v + now});
            now += ans_tree[i].n;
            n -= ans_tree[i].n;
            if(n == 0) break;
        }
        cout << "YES\n";
        cout << vec.size() << '\n';
        for(auto [x,y] : vec) cout << x << ' ' << y << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    init();
    solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 61ms
memory: 12872kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 49ms
memory: 12668kb

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

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 45ms
memory: 12824kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 57ms
memory: 12824kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

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

input:

5

output:

NO

result:

ok Everything ok

Test #7:

score: 0
Accepted
time: 53ms
memory: 12820kb

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

input:

8

output:

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

result:

ok Everything ok

Test #9:

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

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

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

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

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

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

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

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

input:

16

output:

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

result:

ok Everything ok

Test #17:

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

input:

17

output:

YES
14
2 3
2 4
4 5
2 6
6 7
7 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: 61ms
memory: 12956kb

input:

18

output:

YES
15
2 3
2 4
4 5
2 6
6 7
7 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: 56ms
memory: 12764kb

input:

19

output:

YES
16
2 3
2 4
4 5
2 6
6 7
7 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: -100
Wrong Answer
time: 60ms
memory: 12860kb

input:

598

output:

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

result:

wrong answer Not asymmetric