#1158057 (C++23) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: Enderaoe Lyther
• 提出日時: 2026-04-17 21:51:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,285 ms / 2,000 ms
• コード長: 4,736 bytes
• コンパイル時間: 2,402 ms
• コンパイル使用メモリ: 184,704 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-17 21:51:51
• 合計ジャッジ時間: 24,108 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
other	AC * 29

ソースコード

#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>

static constexpr int MAX_N = 100;
static constexpr int MAX_SUM = 200 * MAX_N;

static bool is_square_sum[MAX_SUM + 1];

struct Edge {
  int to;
  int w;
  int id;
};

static std::vector<Edge> adj[MAX_N + 1];

static bool dfs_square(int u, int target, std::bitset<MAX_N + 1> &vis, int sm) {
  if (u == target) {
    return sm <= MAX_SUM && is_square_sum[sm];
  }
  for (const Edge &e : adj[u]) {
    if (vis.test(static_cast<size_t>(e.to))) {
      continue;
    }
    int nsm = sm + e.w;
    if (nsm > MAX_SUM) {
      continue;
    }
    vis.set(static_cast<size_t>(e.to));
    if (dfs_square(e.to, target, vis, nsm)) {
      return true;
    }
    vis.reset(static_cast<size_t>(e.to));
  }
  return false;
}

static bool pair_ok(int i, int j) {
  if (i > j) {
    std::swap(i, j);
  }
  std::bitset<MAX_N + 1> vis;
  vis.set(static_cast<size_t>(i));
  return dfs_square(i, j, vis, 0);
}

static bool new_vertex_ok(int nv) {
  for (int i = 1; i < nv; ++i) {
    if (!pair_ok(i, nv)) {
      return false;
    }
  }
  return true;
}

struct StoredEdge {
  int u;
  int v;
  int w;
  int id;
};

static bool rec_build(int nv, int N, std::vector<StoredEdge> &edges,
                      std::vector<bool> &used_w, int &next_id) {
  if (nv == N + 1) {
    return true;
  }
  const int pairs[3][2] = {{1, 2}, {1, 3}, {2, 3}};
  for (const auto *pr : pairs) {
    const int uu = pr[0];
    const int vv = pr[1];
    for (int a = 1; a <= 200; ++a) {
      if (used_w[static_cast<size_t>(a)]) {
        continue;
      }
      for (int b = 1; b <= 200; ++b) {
        if (a == b || used_w[static_cast<size_t>(b)]) {
          continue;
        }
        const int id1 = next_id + 1;
        const int id2 = next_id + 2;
        adj[uu].push_back({nv, a, id1});
        adj[nv].push_back({uu, a, id1});
        adj[vv].push_back({nv, b, id2});
        adj[nv].push_back({vv, b, id2});
        if (new_vertex_ok(nv)) {
          edges.push_back({uu, nv, a, id1});
          edges.push_back({vv, nv, b, id2});
          used_w[static_cast<size_t>(a)] = true;
          used_w[static_cast<size_t>(b)] = true;
          next_id += 2;
          if (rec_build(nv + 1, N, edges, used_w, next_id)) {
            return true;
          }
          next_id -= 2;
          used_w[static_cast<size_t>(a)] = false;
          used_w[static_cast<size_t>(b)] = false;
          edges.pop_back();
          edges.pop_back();
        }
        adj[uu].pop_back();
        adj[nv].pop_back();
        adj[vv].pop_back();
        adj[nv].pop_back();
      }
    }
  }
  return false;
}

static bool dfs_path(int u, int target, std::bitset<MAX_N + 1> &vis, int sm,
                     std::vector<int> &epath) {
  if (u == target) {
    return sm <= MAX_SUM && is_square_sum[sm];
  }
  for (const Edge &e : adj[u]) {
    if (vis.test(static_cast<size_t>(e.to))) {
      continue;
    }
    int nsm = sm + e.w;
    if (nsm > MAX_SUM) {
      continue;
    }
    vis.set(static_cast<size_t>(e.to));
    epath.push_back(e.id);
    if (dfs_path(e.to, target, vis, nsm, epath)) {
      return true;
    }
    epath.pop_back();
    vis.reset(static_cast<size_t>(e.to));
  }
  return false;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  for (int k = 0; k * k <= MAX_SUM; ++k) {
    is_square_sum[k * k] = true;
  }

  int N;
  std::cin >> N;

  std::vector<StoredEdge> edges;

  if (N == 2) {
    edges.push_back({1, 2, 1, 1});
    adj[1].push_back({2, 1, 1});
    adj[2].push_back({1, 1, 1});
  } else {
    edges.push_back({1, 2, 16, 1});
    edges.push_back({2, 3, 9, 2});
    edges.push_back({1, 3, 25, 3});
    adj[1].push_back({2, 16, 1});
    adj[2].push_back({1, 16, 1});
    adj[2].push_back({3, 9, 2});
    adj[3].push_back({2, 9, 2});
    adj[1].push_back({3, 25, 3});
    adj[3].push_back({1, 25, 3});

    std::vector<bool> used_w(201, false);
    used_w[16] = used_w[9] = used_w[25] = true;
    int next_id = 3;
    if (!rec_build(4, N, edges, used_w, next_id)) {
      return 1;
    }
  }

  for (int v = 1; v <= N; ++v) {
    std::sort(adj[v].begin(), adj[v].end(),
              [](const Edge &a, const Edge &b) { return a.to < b.to; });
  }

  std::cout << edges.size() << '\n';
  for (const auto &e : edges) {
    std::cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
  }

  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      std::bitset<MAX_N + 1> vis;
      vis.set(static_cast<size_t>(i));
      std::vector<int> epath;
      dfs_path(i, j, vis, 0, epath);
      std::cout << epath.size();
      for (int eid : epath) {
        std::cout << ' ' << eid;
      }
      std::cout << '\n';
    }
  }
  return 0;
}