#1182189 (C++23) No.3743 World Mapper

• 問題: No.3743 World Mapper
• ユーザー: 👑 kencho
• 提出日時: 2026-09-03 05:17:39
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,041 bytes
• コンパイル時間: 3,014 ms
• コンパイル使用メモリ: 358,896 KB
• 実行使用メモリ: 29,276 KB
• 最終ジャッジ日時: 2026-09-19 13:08:54
• 合計ジャッジ時間: 81,778 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

サブタスク	配点	結果
部分点1	10 %	AC * 4
部分点2	10 %	AC * 9
部分点3	10 %	AC * 9 WA * 5
部分点4	10 %	AC * 9 WA * 10
部分点5	10 %	AC * 9 WA * 15
部分点6	10 %	AC * 9 WA * 20
部分点7	10 %	AC * 9 WA * 25
部分点8	10 %	AC * 9 WA * 30
部分点9	10 %	AC * 9 WA * 35
満点	10 %	AC * 9 WA * 40
合計	5 * 20% = 100 点

ソースコード

#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; };
struct Pair { int s, t; };

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;
}

vector<vector<pair<int, int>>> graph(int v, const vector<Edge>& e) {
    vector<vector<pair<int, int>>> g(v);
    for (int i = 0; i < (int)e.size(); ++i) {
        g[e[i].u].push_back({e[i].v, i});
        g[e[i].v].push_back({e[i].u, i});
    }
    return g;
}

// trueなら重複を発見。time_upなら探索を打ち切った。
bool collision(int v, const vector<Edge>& e, const vector<vector<pair<int, int>>>& g,
               Pair& a, Pair& b, Clock::time_point deadline, bool& time_up) {
    unordered_map<ll, Pair> seen;
    seen.reserve((size_t)v * (v - 1) / 2);
    vector<ll> dist(v);
    for (int s = 0; s < v; ++s) {
        if (Clock::now() >= deadline) { time_up = true; return false; }
        fill(dist.begin(), dist.end(), (1LL << 60));
        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, id] : g[x]) if (dist[y] > d + e[id].w) {
                dist[y] = d + e[id].w;
                pq.push({dist[y], y});
            }
        }
        for (int t = s + 1; t < v; ++t) {
            auto [it, fresh] = seen.emplace(dist[t], Pair{s, t});
            if (!fresh) { a = it->second; b = {s, t}; return true; }
        }
    }
    return false;
}

vector<int> shortest_path(Pair p, const vector<Edge>& e,
                          const vector<vector<pair<int, int>>>& g) {
    int v = g.size();
    vector<ll> dist(v, (1LL << 60));
    vector<int> pv(v, -1), pe(v, -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    dist[p.s] = 0; pq.push({0, p.s});
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d != dist[x]) continue;
        for (auto [y, id] : g[x]) if (dist[y] > d + e[id].w) {
            dist[y] = d + e[id].w; pv[y] = x; pe[y] = id;
            pq.push({dist[y], y});
        }
    }
    vector<int> path;
    for (int x = p.t; x != p.s; x = pv[x]) path.push_back(pe[x]);
    return path;
}

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);
    auto g = graph(v, e);
    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));
    int steps = 0;
    for (auto& x : e) x.w = weight(rng);
    while (Clock::now() < deadline) {
        Pair a, b; bool time_up = false;
        bool bad = collision(v, e, g, a, b, deadline, time_up);
        if (time_up) break;
        if (!bad) { output(n, e); return 0; }
        Pair chosen = (rng() & 1) ? a : b;
        auto path = shortest_path(chosen, e, g);
        int id = path[rng() % path.size()];
        int delta = (rng() & 1) ? 1 : -1;
        if (e[id].w + delta < 1 || e[id].w + delta > MAX_W) delta = -delta;
        e[id].w += delta;
        if (++steps % 2000 == 0) for (auto& x : e) x.w = weight(rng);
    }
    cout << -1 << '\n';
}