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

• 問題: No.3506 All Distance is Square Number
• ユーザー: Azaki
• 提出日時: 2026-04-18 12:54:03
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,979 bytes
• コンパイル時間: 2,950 ms
• コンパイル使用メモリ: 360,348 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2026-04-18 12:54:40
• 合計ジャッジ時間: 10,312 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
other	AC * 3 WA * 7 TLE * 1 -- * 18

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
};

static const int MAXW = 200;

int N;
vector<Edge> edges;
vector<vector<pair<int,int>>> g; // to, edge_id(1-based)
set<int> sq;

bool isSquare(int x) {
    return sq.count(x);
}

bool dfs_path(int cur, int target, vector<int>& vis, vector<int>& path,
              int sum, vector<int>& ans) {
    if (cur == target) {
        if (isSquare(sum)) {
            ans = path;
            return true;
        }
        return false;
    }
    vis[cur] = 1;
    for (auto [to, eid] : g[cur]) {
        if (vis[to]) continue;
        path.push_back(eid);
        if (dfs_path(to, target, vis, path, sum + edges[eid - 1].w, ans)) {
            return true;
        }
        path.pop_back();
    }
    vis[cur] = 0;
    return false;
}

bool find_any_square_path(int s, int t, vector<int>& ans) {
    vector<int> vis(N + 1, 0), path;
    ans.clear();
    return dfs_path(s, t, vis, path, 0, ans);
}

bool check_all(vector<vector<int>>& allPaths) {
    allPaths.clear();
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            vector<int> p;
            if (!find_any_square_path(i, j, p)) return false;
            allPaths.push_back(p);
        }
    }
    return true;
}

void build_graph(const vector<pair<int,int>>& extraEdges,
                 const vector<int>& weights) {
    edges.clear();

    // path edges
    for (int i = 1; i < N; i++) {
        edges.push_back({i, i + 1, weights[i - 1]});
    }
    // extra edges
    for (int i = 0; i < (int)extraEdges.size(); i++) {
        edges.push_back({extraEdges[i].first, extraEdges[i].second,
                         weights[N - 1 + i]});
    }

    g.assign(N + 1, {});
    for (int i = 0; i < (int)edges.size(); i++) {
        int id = i + 1;
        g[edges[i].u].push_back({edges[i].v, id});
        g[edges[i].v].push_back({edges[i].u, id});
    }
}

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

    cin >> N;

    for (int i = 1; i * i <= 10000; i++) sq.insert(i * i);

    // Chỉ là một số pattern thử nghiệm.
    // Bạn có thể đổi / thêm pattern khác.
    vector<vector<pair<int,int>>> patterns;

    // Pattern 1: thêm (1,3), (1,4), ..., (1,N)
    {
        vector<pair<int,int>> ex;
        for (int v = 3; v <= N; v++) ex.push_back({1, v});
        patterns.push_back(ex);
    }

    // Pattern 2: thêm (i, i+2)
    {
        vector<pair<int,int>> ex;
        for (int i = 1; i + 2 <= N; i++) ex.push_back({i, i + 2});
        patterns.push_back(ex);
    }

    // Pattern 3: xen kẽ một ít cạnh về 1 và cạnh chéo
    {
        vector<pair<int,int>> ex;
        for (int i = 3; i <= N; i++) {
            if (i & 1) ex.push_back({1, i});
            else if (i - 2 >= 1) ex.push_back({i - 2, i});
        }
        patterns.push_back(ex);
    }

    mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

    for (auto& extraEdges : patterns) {
        int M = (N - 1) + (int)extraEdges.size();
        if (M > 2 * N - 3) continue;

        vector<int> pool(MAXW);
        iota(pool.begin(), pool.end(), 1);

        for (int attempt = 0; attempt < 30000; attempt++) {
            shuffle(pool.begin(), pool.end(), rng);
            vector<int> weights(pool.begin(), pool.begin() + M);

            build_graph(extraEdges, weights);

            vector<vector<int>> allPaths;
            if (check_all(allPaths)) {
                cout << M << '\n';
                for (auto &e : edges) {
                    cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
                }
                for (auto &p : allPaths) {
                    cout << p.size();
                    for (int x : p) cout << ' ' << x;
                    cout << '\n';
                }
                return 0;
            }
        }
    }

    // Không tìm được bằng brute thử nghiệm
    cout << -1 << '\n';
    return 0;
}