QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359385#8215. Isomorphic Delightinstallb#WA 98ms14508kbC++237.2kb2024-03-20 17:17:182024-03-20 17:17:19

Judging History

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

  • [2024-03-20 17:17:19]
  • 评测
  • 测评结果:WA
  • 用时:98ms
  • 内存:14508kb
  • [2024-03-20 17:17:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int SZ = 18;
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);
        dfs_hash(1,0);
        for(int i = 1;i <= cur.n;i ++){
            set <pair <int,int> > st; int cnt = 0;
            for(int j : G[i]){
                if(j != fa[i]) cnt ++,st.insert({h[0][j],h[1][j]});
            }
            if(st.size() < cnt) return;
        }
        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);
        }
    }
}

map <pair <int,int>,int> vis;
map <pair <pair <int,int>,pair <int,int> >,int> vis_double;

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);
        
        // set <pair <int,int> > st;
        // for(int i = 1;i <= cur.n;i ++){
        //     dfs_hash(i,0);
        //     st.insert({h[0][i],h[1][i]});
        // }
        // if(st.size() < cur.n) return;

        auto [u,v] = calc_cen(cur.n);
        if(v == -1){
            dfs_hash(u,0);
            if(vis[{h[0][u],h[1][u]}]) return;
            vis[{h[0][u],h[1][u]}] = 1;
        }
        else{
            dfs_hash(u,0);
            set <pair <int,int> > st; int cc = 0;
            for(int w : G[u]){
                if(w == v) continue;
                st.insert({h[0][w],h[1][w]}); cc ++;
            }
            for(int w : G[v]){
                if(w == u) continue;
                st.insert({h[0][w],h[1][w]}); cc ++;
            }
            if(st.size() < cc) return;

            pair <int,int> pl,pr;
            pl = {h[0][u],h[1][u]};
            dfs_hash(v,0);
            pr = {h[0][v],h[1][v]};
            if(pl > pr) swap(pl,pr);
            if(vis_double[{pl,pr}]) return;
            vis_double[{pl,pr}] = 1;
        }
        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 i = 1;i <= SZ;i ++){
    //     cout << "rooted tree size " << i << " : \n";
    //     cout << tr[i].size() << '\n';
    //     for(auto u : tr[i]){
    //         for(auto [x,y] : u.E) cout << x << ',' << y << ' ';
    //         cout << '\n';
    //     }
    // }
    for(int cur_sz = 7;cur_sz <= SZ;cur_sz ++){
        vis.clear();
        vis_double.clear();
        dfs(1,cur_sz - 1,cur_sz);
    }
    sort(ans_tree.begin(),ans_tree.end(),[&](tree x,tree y){ return x.n < y.n; });

    // for(auto tr : ans_tree){
    //     cout << tr.n << " : ";
    //     for(auto [u,v] : tr.E) cout << u << ',' << v << ' ';
    //     cout << '\n';
    // }
    // cout << "COUNT = " << ans_tree.size() << '\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: 95ms
memory: 14156kb

input:

1

output:

YES
0

result:

ok Everything ok

Test #2:

score: 0
Accepted
time: 93ms
memory: 14332kb

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

input:

4

output:

NO

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 93ms
memory: 14148kb

input:

2

output:

NO

result:

ok Everything ok

Test #5:

score: 0
Accepted
time: 92ms
memory: 14212kb

input:

3

output:

NO

result:

ok Everything ok

Test #6:

score: 0
Accepted
time: 97ms
memory: 14020kb

input:

5

output:

NO

result:

ok Everything ok

Test #7:

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 0
Accepted
time: 95ms
memory: 14508kb

input:

598

output:

YES
544
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
17 19
19 20
20 21
17 22
22 23
22 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
32 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
50 52
52 53
54 55
55 56
55 57
57 58
54 59
5...

result:

ok Everything ok

Test #21:

score: 0
Accepted
time: 95ms
memory: 14264kb

input:

245

output:

YES
221
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
17 19
19 20
20 21
17 22
22 23
22 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
32 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
50 52
52 53
54 55
55 56
55 57
57 58
54 59
5...

result:

ok Everything ok

Test #22:

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

input:

793

output:

YES
724
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
17 19
19 20
20 21
17 22
22 23
22 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
32 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
50 52
52 53
54 55
55 56
55 57
57 58
54 59
5...

result:

ok Everything ok

Test #23:

score: 0
Accepted
time: 90ms
memory: 14028kb

input:

133

output:

YES
119
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
17 19
19 20
20 21
17 22
22 23
22 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
32 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
50 52
52 53
54 55
55 56
55 57
57 58
54 59
5...

result:

ok Everything ok

Test #24:

score: -100
Wrong Answer
time: 95ms
memory: 14420kb

input:

681

output:

YES
621
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
17 19
19 20
20 21
17 22
22 23
22 24
24 25
26 27
26 28
28 29
29 30
26 31
31 32
32 33
33 34
35 36
36 37
36 38
38 39
35 40
40 41
41 42
42 43
44 45
45 46
44 47
47 48
48 49
44 50
50 51
50 52
52 53
54 55
55 56
55 57
57 58
54 59
5...

result:

wrong answer contestant's solution is worse (more edges) than jury's