結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 06:15:56
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 3,283 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,831 ms
コンパイル使用メモリ 235,044 KB
実行使用メモリ 11,424 KB
最終ジャッジ日時 2026-04-18 06:16:31
合計ジャッジ時間 12,374 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <random>
using namespace std;
struct Edge {
    int to;
    int weight;
    int id;
};
int N;
vector<vector<Edge>> adj;
vector<pair<pair<int, int>, int>> edges_output;
vector<int> path_res;
vector<int> current_path;
bool found_path;
int dfs_steps;
bool is_sq[40005];
void dfs(int u, int target, int sum, vector<bool>& vis) {
    if (found_path || dfs_steps > 3000) return;
    dfs_steps++;
    if (u == target) {
        if (sum < 40005 && is_sq[sum]) {
            found_path = true;
            path_res = current_path;
        }
        return;
    }
    for (const auto& edge : adj[u]) {
        if (!vis[edge.to]) {
            vis[edge.to] = true;
            current_path.push_back(edge.id);
            dfs(edge.to, target, sum + edge.weight, vis);
            if (found_path) return;
            current_path.pop_back();
            vis[edge.to] = false;
        }
    }
}
bool check_all_pairs() {
    for (int d = 1; d < N; ++d) {
        for (int i = 1; i <= N - d; ++i) {
            int j = i + d;
            found_path = false;
            dfs_steps = 0;
            vector<bool> vis(N + 1, false);
            current_path.clear();
            vis[i] = true;
            dfs(i, j, 0, vis);
            if (!found_path) return false;
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N)) return 0;
    for (int i = 0; i < 40005; ++i) {
        is_sq[i] = false;
    }
    for (int i = 1; i * i < 40005; ++i) {
        is_sq[i * i] = true;
    }
    vector<int> even_weights;
    for (int i = 2; i <= 200; i += 2) {
        even_weights.push_back(i);
    }
    mt19937 rng(1337);
    while (true) {
        shuffle(even_weights.begin(), even_weights.end(), rng);
        adj.assign(N + 1, vector<Edge>());
        edges_output.clear();
        int edge_count = 1;
        for (int i = 1; i < N; ++i) {
            int weight = 2 * i - 1;
            adj[i].push_back({i + 1, weight, edge_count});
            adj[i + 1].push_back({i, weight, edge_count});
            edges_output.push_back({{i, i + 1}, weight});
            edge_count++;
        }
        for (int i = 1; i <= N - 2; ++i) {
            int weight = even_weights[i - 1];
            adj[i].push_back({i + 2, weight, edge_count});
            adj[i + 2].push_back({i, weight, edge_count});
            edges_output.push_back({{i, i + 2}, weight});
            edge_count++;
        }
        if (check_all_pairs()) {
            break;
        }
    }
    cout << edges_output.size() << "\n";
    for (const auto& e : edges_output) {
        cout << e.first.first << " " << e.first.second << " " << e.second << "\n";
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            found_path = false;
            dfs_steps = 0;
            vector<bool> vis(N + 1, false);
            current_path.clear();
            vis[i] = true;
            dfs(i, j, 0, vis);
            cout << path_res.size() << "\n";
            for (int k = 0; k < path_res.size(); ++k) {
                cout << path_res[k] << (k == path_res.size() - 1 ? "" : " ");
            }
            cout << "\n";
        }
    }
    return 0;
}
0