#783424 (C++14) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	oshamashama
提出日時	2022-07-30 17:59:19
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,000 bytes
コンパイル時間	2,550 ms
実行使用メモリ	6,952 KB
スコア	7,447,733
最終ジャッジ日時	2022-07-30 18:00:18
合計ジャッジ時間	33,541 ms
ジャッジサーバーID （参考情報）	judge14 / judge10

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	905 ms 6,948 KB
testcase_01	AC	935 ms 4,908 KB
testcase_02	AC	938 ms 6,948 KB
testcase_03	AC	915 ms 4,908 KB
testcase_04	AC	941 ms 6,948 KB
testcase_05	AC	905 ms 6,948 KB
testcase_06	AC	940 ms 4,900 KB
testcase_07	AC	905 ms 4,900 KB
testcase_08	AC	938 ms 4,900 KB
testcase_09	AC	907 ms 4,900 KB
testcase_10	AC	937 ms 4,900 KB
testcase_11	AC	905 ms 4,904 KB
testcase_12	AC	937 ms 4,904 KB
testcase_13	AC	909 ms 4,904 KB
testcase_14	AC	913 ms 4,904 KB
testcase_15	AC	910 ms 6,952 KB
testcase_16	AC	912 ms 4,904 KB
testcase_17	AC	936 ms 4,904 KB
testcase_18	AC	908 ms 4,900 KB
testcase_19	WA	-
testcase_20	AC	934 ms 4,900 KB
testcase_21	AC	908 ms 4,904 KB
testcase_22	AC	925 ms 4,904 KB
testcase_23	AC	910 ms 4,904 KB
testcase_24	AC	914 ms 4,904 KB
testcase_25	AC	933 ms 6,948 KB
testcase_26	AC	910 ms 4,900 KB
testcase_27	AC	905 ms 4,900 KB
testcase_28	AC	934 ms 4,900 KB
testcase_29	AC	906 ms 4,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;
const long long alpha = 5;
typedef long long ll;
struct solve
{
    ll N, M;
    ll best_score;
    vector<pair<ll, ll>> planet_coordinate;
    vector<pair<ll, ll>> station_coordinate;
    vector<pair<ll, ll>> best_planet_coordinate;
    vector<pair<ll, ll>> best_station_coordinate;
    vector<vector<ll>> m;
    vector<ll> d;
    vector<ll> last;
    solve()
    {
        cin >> N >> M;
        best_score = 0;
        best_planet_coordinate.resize(N);
        best_station_coordinate.resize(M);
        planet_coordinate.resize(N);
        station_coordinate.resize(M);
        m.resize(N + M, vector<ll>(N + M));
        d.resize(N + M, 1e18);
        last.resize(N + M, 1e18);
        for (int i = 0; i < N; i++)
        {
            cin >> planet_coordinate.at(i).first >> planet_coordinate.at(i).second;
        }
    }

    ll dist(pair<ll, ll> a, pair<ll, ll> b)
    {
        return ((a.first - b.first) * (a.first - b.first) +
                (a.second - b.second) * (a.second - b.second));
    }

    ll distance(int i, int j)
    {
        return dist((i < N ? planet_coordinate.at(i) : station_coordinate.at(i - N)),
                    (j < N ? planet_coordinate.at(j) : station_coordinate.at(j - N))) *
               (i < N ? 5 : 1) *
               (j < N ? 5 : 1);
    }

    ll get_shortest(int &start, vector<bool> &used, queue<int> &q)
    {
        for (int i = 0; i < N + M; i++)
        {
            for (int j = 0; j < N + M; j++)
            {
                m.at(i).at(j) = distance(i, j);
            }
        }
        priority_queue<pair<ll, ll>> pq;
        d.resize(N + M, 1e18);
        pq.push(make_pair(0, start));
        ll Md = 1e18;
        int ind = 0;
        for (int i = 0; i < N + M; i++)
        {
            // cerr << "hoge" << d.at(i) << endl;
            d.at(i) = 1e18;
        }
        d.at(start) = 0;

        while (pq.size())
        {
            int now = pq.top().second;
            pq.pop();
            for (int i = 0; i < N + M; i++)
            {
                int next = i;
                // cerr << "-----" << now << ' ' << next << endl;
                // cerr << d.size() << endl;
                // cerr << m.at(0).size() << endl;
                // cerr << d.at(next) << endl;
                if (d.at(next) > d.at(now) + m.at(now).at(next))
                {
                    d.at(next) = d.at(now) + m.at(now).at(next);
                    last.at(next) = now;
                    // cout << "Md " << endl;
                    if (N <= next)
                    {
                        pq.push(make_pair(d.at(next), next));
                    }
                    else if (Md > d.at(next) &&
                             used.at(next) == false)
                    {
                        // cout << "/* code */" << endl;
                        Md = d.at(next);
                        ind = next;
                    }
                }
            }
        }
        // cout << ind << endl;
        int next = ind;
        if (ind != -1)
        {
            stack<int> s;
            while (ind != start)
            {
                s.push(ind);
                // cerr << "check " << ind << ' ' << last.at(ind) << endl;
                ind = last.at(ind);
            }
            while (s.size())
            {
                q.push(s.top());
                s.pop();
            }
        }
        start = next;
        used.at(start) = true;
        return d.at(start);
    }

    void print_ans()
    {

        std::random_device rd;
        std::default_random_engine eng(rd());
        std::uniform_int_distribution<int> distr(200, 800);
        std::uniform_int_distribution<int> distr2(-40, 40);

        ll ccc = 10;
        queue<int> best_q;
        ll time_limit = 900000;

        // while (clock() < time_limit / 2)
        // {
        //     for (int i = 0; i < M; i++)
        //     {
        //         station_coordinate.at(i) = make_pair(distr(eng), distr(eng));
        //         // cerr << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
        //     }
        //     queue<int> q;
        //     q.push(0);
        //     vector<bool> used(N + M, 0);
        //     used.at(0) = true;
        //     int start = 0;
        //     ll sum = 0;
        //     for (int i = 0; i < N; i++)
        //     {
        //         sum += get_shortest(start, used, q);
        //         // cout << start << endl;
        //     }
        //     ll now_score = 1000000000 / (1000 + sqrt(sum));
        //     if (now_score > best_score)
        //     {
        //         best_q = q;
        //         best_planet_coordinate = planet_coordinate;
        //         best_station_coordinate = station_coordinate;
        //         best_score = now_score;
        //     }
        // }
        station_coordinate.at(0) = make_pair(300, 300);
        station_coordinate.at(1) = make_pair(700, 300);
        station_coordinate.at(2) = make_pair(300, 700);
        station_coordinate.at(3) = make_pair(700, 700);
        station_coordinate.at(4) = make_pair(300, 500);
        station_coordinate.at(5) = make_pair(500, 300);
        station_coordinate.at(6) = make_pair(700, 500);
        station_coordinate.at(7) = make_pair(500, 700);

        while (clock() < time_limit)
        {
            for (int i = 0; i < M; i++)
            {
                station_coordinate.at(i) = make_pair(station_coordinate.at(i).first + distr2(eng),
                                                     station_coordinate.at(i).second + distr2(eng));
                // cerr << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
            }
            queue<int> q;
            q.push(0);
            vector<bool> used(N + M, 0);
            used.at(0) = true;
            int start = 0;
            ll sum = 0;
            for (int i = 0; i < N; i++)
            {
                sum += get_shortest(start, used, q);
                // cout << start << endl;
            }
            ll now_score = 1000000000 / (1000 + sqrt(sum));
            if (now_score > best_score)
            {
                best_q = q;
                best_planet_coordinate = planet_coordinate;
                best_station_coordinate = station_coordinate;
                best_score = now_score;
            }
        }
        cerr << best_score << endl;
        for (int i = 0; i < M; i++)
        {
            cout << best_station_coordinate.at(i).first << ' ' << best_station_coordinate.at(i).second << endl;
        }
        cout << best_q.size() << endl;
        while (best_q.size())
        {
            int now = best_q.front();
            // cout << now << endl;
            cout << 1 + now / N
                 << ' '
                 << now % N + 1
                 << endl;
            best_q.pop();
        }
    }
};

int main()
{
    solve s;
    s.print_ans();
    return 0;
}

yukicoder

結果

テストケース

ソースコード