結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 rumblycascade7
|
| 提出日時 | 2026-04-18 09:08:14 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,748 bytes |
| 記録 | |
| コンパイル時間 | 3,324 ms |
| コンパイル使用メモリ | 363,008 KB |
| 実行使用メモリ | 9,984 KB |
| 最終ジャッジ日時 | 2026-04-18 09:09:38 |
| 合計ジャッジ時間 | 17,791 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 9 WA * 4 TLE * 1 -- * 15 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
namespace {
static inline bool is_square(int x) {
if (x <= 0) return false;
int r = (int)std::sqrt((long double)x);
while ((long long)r * r < x) ++r;
while ((long long)r * r > x) --r;
return r * r == x;
}
struct Graph {
int N = 0;
vector<pair<int,int>> edges;
vector<int> w;
vector<vector<pair<int,int>>> adj;
Graph() = default;
Graph(int n, vector<pair<int,int>> e): N(n), edges(std::move(e)) {
adj.assign(N + 1, {});
for (int i = 0; i < (int)edges.size(); ++i) {
auto [u, v] = edges[i];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
}
int M() const { return (int)edges.size(); }
};
struct Constructor {
int N;
mt19937_64 rng;
chrono::steady_clock::time_point ts;
Constructor(int n): N(n) {
rng.seed((uint64_t)chrono::high_resolution_clock::now().time_since_epoch().count());
ts = chrono::steady_clock::now();
}
bool time_ok(int ms_limit = 1800) const {
auto now = chrono::steady_clock::now();
int ms = (int)chrono::duration_cast<chrono::milliseconds>(now - ts).count();
return ms < ms_limit;
}
vector<pair<int,int>> make_fan_edges() {
vector<pair<int,int>> e;
for (int k = 1; k <= N - 1; ++k) e.push_back({k, k + 1});
for (int k = 3; k <= N; ++k) e.push_back({1, k});
return e;
}
vector<pair<int,int>> make_double_star_edges() {
vector<pair<int,int>> e;
e.push_back({1, 2});
for (int k = 3; k <= N; ++k) e.push_back({1, k});
for (int k = 3; k <= N; ++k) e.push_back({2, k});
return e;
}
vector<pair<int,int>> make_random_2tree_edges() {
vector<pair<int,int>> e;
e.push_back({1, 2});
for (int v = 3; v <= N; ++v) {
int a = uniform_int_distribution<int>(1, v - 1)(rng);
int b = uniform_int_distribution<int>(1, v - 2)(rng);
if (b >= a) ++b;
e.push_back({v, a});
e.push_back({v, b});
}
return e;
}
bool dfs_find_path(const Graph& g, int s, int t, vector<int>& out) {
const int MAX_SUM = 200 * (g.N - 1);
static vector<int> squares;
if (squares.empty()) {
for (int i = 1; i * i <= MAX_SUM; ++i) squares.push_back(i * i);
}
vector<int> vis(g.N + 1, 0), cur;
vis[s] = 1;
bool ok = false;
function<void(int,int)> dfs = [&](int u, int sum) {
if (ok) return;
if ((int)cur.size() >= g.N) return;
if (u == t) {
if (is_square(sum)) {
out = cur;
ok = true;
}
return;
}
for (auto [v, eid] : g.adj[u]) {
if (vis[v]) continue;
vis[v] = 1;
cur.push_back(eid);
dfs(v, sum + g.w[eid]);
cur.pop_back();
vis[v] = 0;
if (ok) return;
}
};
dfs(s, 0);
return ok;
}
bool verify_and_collect(Graph& g, vector<vector<vector<int>>>& paths) {
if ((int)g.w.size() != g.M()) return false;
vector<int> seen(201, 0);
for (int x : g.w) {
if (x < 1 || x > 200 || seen[x]) return false;
seen[x] = 1;
}
paths.assign(N + 1, vector<vector<int>>(N + 1));
for (int i = 1; i <= N; ++i) {
for (int j = i + 1; j <= N; ++j) {
vector<int> p;
if (!dfs_find_path(g, i, j, p)) return false;
paths[i][j] = std::move(p);
}
}
return true;
}
void set_random_distinct_weights(Graph& g) {
vector<int> vals(200);
iota(vals.begin(), vals.end(), 1);
shuffle(vals.begin(), vals.end(), rng);
g.w.assign(vals.begin(), vals.begin() + g.M());
}
bool solve(Graph& best, vector<vector<vector<int>>>& best_paths) {
if (N == 2) {
best = Graph(2, {{1,2}});
best.w = {1};
best_paths.assign(3, vector<vector<int>>(3));
best_paths[1][2] = {0};
return true;
}
if (N == 3) {
best = Graph(3, {{1,2},{2,3},{1,3}});
best.w = {16,9,25};
best_paths.assign(4, vector<vector<int>>(4));
best_paths[1][2] = {0};
best_paths[1][3] = {2};
best_paths[2][3] = {1};
return true;
}
while (time_ok()) {
{
Graph g(N, make_fan_edges());
vector<int> used(201, 0);
g.w.clear();
for (int k = 1; k <= N - 1; ++k) {
int x = 2 * k - 1;
g.w.push_back(x);
used[x] = 1;
}
vector<int> pool;
for (int x = 1; x <= 200; ++x) if (!used[x]) pool.push_back(x);
shuffle(pool.begin(), pool.end(), rng);
for (int i = 0; i < N - 2; ++i) g.w.push_back(pool[i]);
vector<vector<vector<int>>> paths;
if (verify_and_collect(g, paths)) {
best = std::move(g);
best_paths = std::move(paths);
return true;
}
}
{
Graph g(N, make_fan_edges());
set_random_distinct_weights(g);
vector<vector<vector<int>>> paths;
if (verify_and_collect(g, paths)) {
best = std::move(g);
best_paths = std::move(paths);
return true;
}
}
{
Graph g(N, make_double_star_edges());
set_random_distinct_weights(g);
vector<vector<vector<int>>> paths;
if (verify_and_collect(g, paths)) {
best = std::move(g);
best_paths = std::move(paths);
return true;
}
}
{
Graph g(N, make_random_2tree_edges());
set_random_distinct_weights(g);
vector<vector<vector<int>>> paths;
if (verify_and_collect(g, paths)) {
best = std::move(g);
best_paths = std::move(paths);
return true;
}
}
}
return false;
}
};
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
Constructor ctor(N);
Graph g;
vector<vector<vector<int>>> paths;
bool ok = ctor.solve(g, paths);
if (!ok) {
vector<pair<int,int>> e;
for (int k = 1; k <= N - 1; ++k) e.push_back({k, k + 1});
for (int k = 3; k <= N; ++k) e.push_back({1, k});
cout << e.size() << '\n';
int w = 1;
for (auto [u, v] : e) cout << u << ' ' << v << ' ' << w++ << '\n';
for (int i = 1; i <= N; ++i) {
for (int j = i + 1; j <= N; ++j) {
cout << 1 << ' ' << 1 << '\n';
}
}
return 0;
}
cout << g.M() << '\n';
for (int i = 0; i < g.M(); ++i) {
auto [u, v] = g.edges[i];
cout << u << ' ' << v << ' ' << g.w[i] << '\n';
}
for (int i = 1; i <= N; ++i) {
for (int j = i + 1; j <= N; ++j) {
auto& p = paths[i][j];
cout << p.size();
for (int eid : p) cout << ' ' << (eid + 1);
cout << '\n';
}
}
return 0;
}