QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#329544 | #8215. Isomorphic Delight | ckiseki | WA | 1ms | 3876kb | C++20 | 3.5kb | 2024-02-16 20:58:50 | 2024-02-16 20:58:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
map<vector<int>, int> mp;
vector<vector<int>> child;
int getId(vector<int> s) {
sort(all(s));
if (auto it = mp.find(s); it != mp.end())
return it->second;
int res = mp[s] = (int)child.size();
child.emplace_back(s);
return res;
}
vector<int> rooted_trees[11];
vector<int> unrooted_trees[22];
vector<int> stk, cur;
void dfs(int rest, int j, int index) {
if (rest == 0) {
cur.push_back(getId(stk));
return;
}
if (j == 0)
return;
if (index == rooted_trees[j].size()) {
dfs(rest, j - 1, 0);
return;
}
dfs(rest, j, index + 1);
stk.push_back(rooted_trees[j][index]);
if (j <= rest) dfs(rest - j, j, index + 1);
stk.pop_back();
}
void dfs_unrooted(int rest, int j, int index) {
if (rest == 0) {
cur.push_back(getId(stk));
return;
}
if (j == 0)
return;
if (index == rooted_trees[j].size()) {
dfs_unrooted(rest, j - 1, 0);
return;
}
dfs_unrooted(rest, j, index + 1);
stk.push_back(rooted_trees[j][index]);
if (j <= rest) dfs_unrooted(rest - j, j, index + 1);
stk.pop_back();
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
rooted_trees[1].emplace_back(getId({}));
for (int i = 2; i <= 10; i++) {
cur.clear();
dfs(i - 1, i - 1, 0);
rooted_trees[i] = cur;
debug(rooted_trees[i].size(), i);
}
int N;
cin >> N;
if (N == 1) {
cout << "YES\n0\n";
return 0;
}
if (N == 6) {
cout << "YES\n";
cout << "6\n";
cout << "1 2\n2 3\n1 3\n3 4\n2 5\n5 6\n";
return 0;
}
if (N < 7) {
cout << "NO\n";
return 0;
}
safe;
int node_id = 0;
vector<vector<int>> g(N);
vector<pair<int,int>> edges;
auto add_edge = [&g, &edges](int a, int b) {
edges.emplace_back(a, b);
g[a].emplace_back(b);
g[b].emplace_back(a);
};
if (N > 7) {
++node_id;
--N;
}
auto Expand = [&](int root) {
auto dfs = [&](auto self, int i) -> int {
int node = node_id++;
for (int j : child[i]) {
int z = self(self, j);
add_edge(node, z);
}
return node;
};
return dfs(dfs, root);
};
for (int n = 2; n <= 21; n++) {
cur.clear();
dfs_unrooted(n - 1, (n - 1) / 2, 0);
for (int x : cur) {
if (N >= n) {
N -= n;
Expand(x);
} else {
goto end;
}
}
if (n % 2 == 0) {
for (int x : rooted_trees[n / 2])
for (int y : rooted_trees[n / 2])
if (x < y) {
if (N >= n) {
N -= n;
int a = Expand(x);
int b = Expand(y);
add_edge(a, b);
} else {
goto end;
}
}
}
debug(n, cur.size());
}
end:
g[node_id - 1];
cout << "YES\n";
cout << edges.size() << '\n';
for (auto [a, b] : edges)
cout << a + 1 << ' ' << b + 1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
1
output:
YES 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
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: 0ms
memory: 3824kb
input:
4
output:
NO
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2
output:
NO
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3
output:
NO
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
5
output:
NO
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
7
output:
YES 6 1 2 3 4 1 3 6 7 5 6 1 5
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
8
output:
YES 6 2 3 4 5 2 4 7 8 6 7 2 6
result:
ok Everything ok
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3640kb
input:
9
output:
YES 6 2 3 4 5 2 4 7 8 6 7 2 6
result:
wrong answer Not asymmetric