結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-19 04:49:42
言語 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,327 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,140 ms
コンパイル使用メモリ 210,204 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2026-04-19 04:50:21
合計ジャッジ時間 8,512 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <random>
using namespace std;
const int MAX_SUM = 40000;
bool is_sq[MAX_SUM + 5];
struct Edge {
    int to;
    int weight;
    int id;
};
int N;
vector<vector<Edge>> adj;
vector<int> current_path;
vector<int> best_path;
bool found_path;
bool visited[105];
void dfs(int u, int target, int sum, int depth) {
    if (found_path) return;
    if (u == target) {
        if (is_sq[sum]) {
            found_path = true;
            best_path = current_path;
        }
        return;
    }
    if (depth == 0) return;
    for (auto& edge : adj[u]) {
        if (!visited[edge.to]) {
            visited[edge.to] = true;
            current_path.push_back(edge.id);
            dfs(edge.to, target, sum + edge.weight, depth - 1);
            current_path.pop_back();
            visited[edge.to] = false;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 1; i * i <= MAX_SUM; ++i) {
        is_sq[i * i] = true;
    }
    if (!(cin >> N)) return 0;
    mt19937 rng(1337);
    vector<int> evens;
    for (int i = 2; i <= 2 * N - 4; i += 2) {
        evens.push_back(i);
    }
    int M = 2 * N - 3;
    vector<vector<int>> ans_paths(N + 1, vector<int>(N + 1));
    vector<vector<int>> output_paths;
    while (true) {
        adj.assign(N + 1, vector<Edge>());
        int edge_id = 1;
        for (int i = 1; i < N; ++i) {
            int u = i, v = i + 1;
            int w = 2 * i - 1;
            adj[u].push_back({v, w, edge_id});
            adj[v].push_back({u, w, edge_id});
            edge_id++;
        }
        shuffle(evens.begin(), evens.end(), rng);
        int even_idx = 0;
        for (int i = 3; i <= N; ++i) {
            int u = 1, v = i;
            int w = evens[even_idx++];
            adj[u].push_back({v, w, edge_id});
            adj[v].push_back({u, w, edge_id});
            edge_id++;
        }
        bool all_ok = true;
        output_paths.clear();
        for (int i = 1; i <= N && all_ok; ++i) {
            for (int j = i + 1; j <= N && all_ok; ++j) {
                found_path = false;
                for (int max_depth = 1; max_depth <= 6; ++max_depth) {
                    fill(visited, visited + N + 1, false);
                    visited[i] = true;
                    current_path.clear();
                    dfs(i, j, 0, max_depth);
                    if (found_path) break;
                }
                if (found_path) {
                    output_paths.push_back(best_path);
                } else {
                    all_ok = false;
                }
            }
        }
        if (all_ok) {
            cout << M << "\n";
            edge_id = 1;
            for (int i = 1; i < N; ++i) {
                cout << i << " " << i + 1 << " " << 2 * i - 1 << "\n";
            }
            even_idx = 0;
            for (int i = 3; i <= N; ++i) {
                cout << 1 << " " << i << " " << evens[even_idx++] << "\n";
            }
            for (const auto& path : output_paths) {
                cout << path.size();
                for (int e : path) {
                    cout << " " << e;
                }
                cout << "\n";
            }
            break;
        }
    }
    return 0;
}
0