QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#329544#8215. Isomorphic DelightckisekiWA 1ms3876kbC++203.5kb2024-02-16 20:58:502024-02-16 20:58:51

Judging History

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

  • [2024-02-16 20:58:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3876kb
  • [2024-02-16 20:58:50]
  • 提交

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