提出 #27902230

---

ソースコード 拡げる

#include <algorithm>
#include <atcoder/dsu>
#include <cmath>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

using namespace std;
using namespace atcoder;

// 頂点の数
constexpr int N = 400;
// 辺の数
constexpr int M = 1995;
// ランダムな辺の生成数
constexpr int EDGE_SET_COUNT = 14;
// 乱数のシード値
constexpr int RANDOM_SEED = 42;
// INF（小さめ）
constexpr int INF = 10000000;

/// 2次元平面上の座標を表す構造体。
struct coordinate {
    int x;
    int y;

    coordinate(int x, int y) : x(x), y(y) {}

    /// 2頂点間のユークリッド距離を求める。
    int get_dist(const coordinate &other) {
        int dx = x - other.x;
        int dy = y - other.y;
        double d = round(sqrt(dx * dx + dy * dy));
        return static_cast<int>(d);
    }
};

/// 入力を表す構造体。
struct input {
    int n;
    int m;
    vector<coordinate> coordinates;
    vector<pair<int, int>> edges;

    input(int n, int m, vector<coordinate> &&coordinates, vector<pair<int, int>> &&edges)
        : n(n), m(m), coordinates(coordinates), edges(edges) {}
};

// ==== プロトタイプ宣言 ====

input read_testcases();
void solve(const input &input);
vector<vector<int>> generate_random_dists(const input &input, int count, int random_seed);
vector<int> calc_euclidean_dists(const input &input);
bool decide_use_or_not(const input &input, int edge_index, int edge_distance, dsu &union_find,
                       const vector<vector<int>> &random_dists);
vector<int> get_sorted_edge_indice(int start_index, const vector<int> &distances);
int kruskal(const input &input, dsu &union_find, const vector<int> &sorted_edge_indice, const vector<int> &distances);

// ==== プロトタイプ宣言ここまで ====

/// エントリポイント。
int main() {
    input input = read_testcases();
    solve(input);
}

/// テストケースを読み込む。
input read_testcases() {
    // 点の座標(x, y)の読み込み
    vector<coordinate> coordinates;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        coordinate coordinate(x, y);
        coordinates.push_back(coordinate);
    }

    // 辺(u, v)の読み込み
    vector<pair<int, int>> edges;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back(make_pair(u, v));
    }

    input input(N, M, move(coordinates), move(edges));
    return input;
}

/// 問題を解く。
void solve(const input &input) {
    // ランダムな辺のリストを生成
    vector<vector<int>> random_dists = generate_random_dists(input, EDGE_SET_COUNT, RANDOM_SEED);

    // 頂点の連結状態を管理するDSU (=Union-Find)
    dsu union_find(input.n);

    // 各辺について採用するかしないか判断していく
    for (int edge_index = 0; edge_index < input.m; edge_index++) {
        // i番目の辺の長さを読み込む
        int edge_distance;
        cin >> edge_distance;

        // 採用するかしないか判断
        bool use = decide_use_or_not(input, edge_index, edge_distance, union_find, random_dists);

        if (use) {
            // 採用する場合は辺で繋げる
            auto [u, v] = input.edges[edge_index];
            union_find.merge(u, v);
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
}

///ランダムな辺の長さのリストをcount個生成する。
///各辺の長さは、辺のユークリッド距離をdとしてd以上3d以下のランダムな値とする。
vector<vector<int>> generate_random_dists(const input &input, int count, int random_seed) {
    // 乱数生成器（メルセンヌ・ツイスタ）の初期化
    mt19937 mt(random_seed);

    // ユークリッド距離を求めておく
    vector<int> euclidean_dists = calc_euclidean_dists(input);

    // 辺の長さの2次元配列
    // M要素の配列がcount個入る
    vector<vector<int>> random_dists(count);

    // 辺の生成
    for (int i = 0; i < count; i++) {
        for (int j = 0; j < input.m; j++) {
            // d以上3d以下の範囲でランダムに辺の長さを決める
            // uniform_int_distributionは指定範囲の整数を一様ランダムに生成するクラス
            uniform_int_distribution<int> rand(euclidean_dists[j], 3 * euclidean_dists[j]);
            int dist = rand(mt);
            random_dists[i].push_back(dist);
        }
    }

    return random_dists;
}

/// 全ての辺のユークリッド距離を計算する。
vector<int> calc_euclidean_dists(const input &input) {
    vector<int> distances;

    for (int i = 0; i < input.m; i++) {
        auto [u, v] = input.edges[i];
        coordinate p = input.coordinates[u];
        coordinate q = input.coordinates[v];
        int dist = p.get_dist(q);
        distances.push_back(dist);
    }

    return distances;
}

/// edge_index番目の辺を採用するかしないか判断する。
bool decide_use_or_not(const input &input, int edge_index, int edge_distance, dsu &union_find,
                       const vector<vector<int>> &random_dists) {
    auto [u, v] = input.edges[edge_index];

    // 既に連結だったら採用しない
    if (union_find.same(u, v)) {
        return false;
    }

    // 採用した場合・しなかった場合のコストの和
    int use_cost_sum = 0;
    int pass_cost_sum = 0;

    // 各ランダムケースに対して、辺を採用する場合と採用しない場合のコストを計算する
    for (int i = 0; i < random_dists.size(); i++) {
        // 予め辺のedge_index+1番目以降のインデックスを距離の昇順で並べ替えておく
        // クラスカル法を2回やるので前計算した方が高速
        vector<int> sorted_edge_indice = get_sorted_edge_indice(edge_index + 1, random_dists[i]);

        // 辺を採用する場合のコスト計算
        // Union-Findをコピーしておく
        dsu union_find_use(union_find);
        union_find_use.merge(u, v);

        // 採用する場合のコストは、edge_index番目の辺のコストとそれ以降のクラスカル法のコストの和
        int use_cost = edge_distance + kruskal(input, union_find_use, sorted_edge_indice, random_dists[i]);
        use_cost_sum += use_cost;

        // 辺を採用しない場合のコスト計算
        dsu union_find_pass(union_find);

        // 採用しない場合のコストは、edge_index+1番目以降のクラスカル法のコスト
        int pass_cost = kruskal(input, union_find_pass, sorted_edge_indice, random_dists[i]);
        pass_cost_sum += pass_cost;
    }

    // 採用した場合のコストの総和が採用しない場合のコストの総和以下であれば採用
    bool use = use_cost_sum <= pass_cost_sum;
    return use;
}

/// start_index以降の辺のインデックスを距離の昇順で並べ替える。
vector<int> get_sorted_edge_indice(int start_index, const vector<int> &distances) {
    // start_index以降のインデックスを列挙
    vector<int> indice;
    indice.reserve(distances.size() - start_index);

    for (int i = start_index; i < distances.size(); i++) {
        indice.push_back(i);
    }

    // 辺の距離の昇順でインデックスを並び替える
    sort(indice.begin(), indice.end(), [&](int a, int b) { return distances[a] < distances[b]; });

    return indice;
}

/// クラスカル法により最小全域木問題を解き、コストの総和を返す。
/// sorted_edge_indiceはdistanceの昇順でソート済みである必要がある。
/// グラフを連結にできない場合はINFを返す。
int kruskal(const input &input, dsu &union_find, const vector<int> &sorted_edge_indice, const vector<int> &distances) {
    // 普通にクラスカル法をやる
    int cost_sum = 0;

    for (int i = 0; i < sorted_edge_indice.size(); i++) {
        int index = sorted_edge_indice[i];
        auto [u, v] = input.edges[index];

        if (!union_find.same(u, v)) {
            union_find.merge(u, v);
            cost_sum += distances[index];
        }
    }

    // グラフが連結になったかどうか判断
    bool connected = union_find.size(0) == input.n;

    if (connected) {
        return cost_sum;
    } else {
        // 連結でない場合はINFを返す
        // オーバーフローに注意
        return INF;
    }
}

提出情報

ジャッジ結果