結果

問題 No.3743 World Mapper
コンテスト
ユーザー 👑 kencho
提出日時 2026-09-03 05:16:53
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,481 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,600 ms
コンパイル使用メモリ 354,656 KB
実行使用メモリ 40,084 KB
最終ジャッジ日時 2026-09-19 13:07:32
合計ジャッジ時間 83,361 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 4
部分点2 10 % AC * 8 WA * 1
部分点3 10 % AC * 8 WA * 6
部分点4 10 % AC * 8 WA * 11
部分点5 10 % AC * 8 WA * 16
部分点6 10 % AC * 8 WA * 21
部分点7 10 % AC * 8 WA * 26
部分点8 10 % AC * 8 WA * 31
部分点9 10 % AC * 8 WA * 36
満点 10 % AC * 8 WA * 41
合計 5 * 10% = 50 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;
using Clock = chrono::steady_clock;
constexpr int MAX_W = 300000;
constexpr double TIME_LIMIT = 1.9;

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

vector<Edge> make_edges(int n) {
    vector<Edge> e;
    for (int r = 0; r + 1 < n; ++r) for (int c = 0; c < n; ++c)
        e.push_back({r * n + c, (r + 1) * n + c, 1});
    for (int r = 0; r < n; ++r) for (int c = 0; c + 1 < n; ++c)
        e.push_back({r * n + c, r * n + c + 1, 1});
    return e;
}

// 1: valid, 0: duplicate, -1: time up
int check(int v, const vector<Edge>& e, Clock::time_point deadline) {
    vector<vector<pair<int, int>>> g(v);
    for (auto [a, b, w] : e) {
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    unordered_set<ll> seen;
    seen.reserve((size_t)v * (v - 1) / 2);
    const ll INF = (1LL << 60);
    vector<ll> dist(v);
    for (int s = 0; s < v; ++s) {
        if (Clock::now() >= deadline) return -1;
        fill(dist.begin(), dist.end(), INF);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        dist[s] = 0; pq.push({0, s});
        while (!pq.empty()) {
            auto [d, x] = pq.top(); pq.pop();
            if (d != dist[x]) continue;
            for (auto [y, w] : g[x]) if (dist[y] > d + w) {
                dist[y] = d + w;
                pq.push({dist[y], y});
            }
        }
        for (int t = s + 1; t < v; ++t)
            if (!seen.insert(dist[t]).second) return 0;
    }
    return 1;
}

void output(int n, const vector<Edge>& e) {
    int k = 0;
    for (int r = 0; r + 1 < n; ++r) {
        for (int c = 0; c < n; ++c) cout << (c ? " " : "") << e[k++].w;
        cout << '\n';
    }
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c + 1 < n; ++c) cout << (c ? " " : "") << e[k++].w;
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    int v = n * n;
    auto e = make_edges(n);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> weight(1, MAX_W);
    auto deadline = Clock::now() + chrono::duration_cast<Clock::duration>(chrono::duration<double>(TIME_LIMIT));
    while (Clock::now() < deadline) {
        for (auto& x : e) x.w = weight(rng);
        int result = check(v, e, deadline);
        if (result == 1) { output(n, e); return 0; }
        if (result < 0) break;
    }
    cout << -1 << '\n';
}
0