QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359465 | #8215. Isomorphic Delight | installb# | AC ✓ | 157ms | 22756kb | C++23 | 5.9kb | 2024-03-20 18:06:27 | 2024-03-20 18:06:28 |
Judging History
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);
}
}
}
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);
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{
pair <int,int> pl,pr,v1,v2;
dfs_hash(u,0);
pl = {h[0][u],h[1][u]};
v1 = {h[0][v],h[1][v]};
dfs_hash(v,0);
pr = {h[0][v],h[1][v]};
v2 = {h[0][u],h[1][u]};
if(v1 == v2) return;
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 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; });
}
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;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 90ms
memory: 14160kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 91ms
memory: 14272kb
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: 98ms
memory: 14040kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 95ms
memory: 14100kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 94ms
memory: 14228kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 94ms
memory: 14220kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 88ms
memory: 13944kb
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: 95ms
memory: 14128kb
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: 91ms
memory: 14180kb
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: 95ms
memory: 14176kb
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: 90ms
memory: 14296kb
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: 94ms
memory: 14228kb
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: 97ms
memory: 14280kb
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: 97ms
memory: 14132kb
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: 97ms
memory: 14168kb
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: 92ms
memory: 14000kb
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: 114ms
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: 92ms
memory: 14044kb
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: 94ms
memory: 14004kb
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: 98ms
memory: 14272kb
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: 93ms
memory: 14172kb
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: 103ms
memory: 14136kb
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: 84ms
memory: 14296kb
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: 0
Accepted
time: 85ms
memory: 14224kb
input:
681
output:
YES 620 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 #25:
score: 0
Accepted
time: 95ms
memory: 14116kb
input:
922
output:
YES 843 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 #26:
score: 0
Accepted
time: 94ms
memory: 13980kb
input:
876
output:
YES 800 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 #27:
score: 0
Accepted
time: 89ms
memory: 14404kb
input:
7740
output:
YES 7191 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 ...
result:
ok Everything ok
Test #28:
score: 0
Accepted
time: 100ms
memory: 14192kb
input:
2460
output:
YES 2268 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 ...
result:
ok Everything ok
Test #29:
score: 0
Accepted
time: 93ms
memory: 14628kb
input:
7533
output:
YES 6998 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 ...
result:
ok Everything ok
Test #30:
score: 0
Accepted
time: 95ms
memory: 14220kb
input:
5957
output:
YES 5527 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 ...
result:
ok Everything ok
Test #31:
score: 0
Accepted
time: 101ms
memory: 16132kb
input:
92651
output:
YES 87225 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...
result:
ok Everything ok
Test #32:
score: 0
Accepted
time: 101ms
memory: 15296kb
input:
58779
output:
YES 55235 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...
result:
ok Everything ok
Test #33:
score: 0
Accepted
time: 85ms
memory: 14520kb
input:
12203
output:
YES 11374 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...
result:
ok Everything ok
Test #34:
score: 0
Accepted
time: 100ms
memory: 15176kb
input:
55627
output:
YES 52258 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...
result:
ok Everything ok
Test #35:
score: 0
Accepted
time: 107ms
memory: 16100kb
input:
99051
output:
YES 93269 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...
result:
ok Everything ok
Test #36:
score: 0
Accepted
time: 148ms
memory: 22756kb
input:
811713
output:
YES 770513 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 5...
result:
ok Everything ok
Test #37:
score: 0
Accepted
time: 120ms
memory: 18364kb
input:
544133
output:
YES 515717 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 5...
result:
ok Everything ok
Test #38:
score: 0
Accepted
time: 114ms
memory: 17292kb
input:
276553
output:
YES 261516 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 5...
result:
ok Everything ok
Test #39:
score: 0
Accepted
time: 122ms
memory: 22632kb
input:
736904
output:
YES 699266 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 5...
result:
ok Everything ok
Test #40:
score: 0
Accepted
time: 157ms
memory: 22548kb
input:
1000000
output:
YES 949834 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 5...
result:
ok Everything ok
Extra Test:
score: 0
Extra Test Passed