#735827 (C++17) No.1599 Hikyaku

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	👑 Nachia
提出日時	2022-01-31 00:28:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,147 ms / 7,500 ms
コード長	6,563 bytes
コンパイル時間	1,510 ms
コンパイル使用メモリ	98,432 KB
実行使用メモリ	60,512 KB
最終ジャッジ日時	2024-06-11 08:35:53
合計ジャッジ時間	35,002 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	167 ms 53,212 KB
testcase_01	AC	199 ms 54,236 KB
testcase_02	AC	210 ms 54,368 KB
testcase_03	AC	153 ms 57,688 KB
testcase_04	AC	1,076 ms 50,776 KB
testcase_05	AC	384 ms 50,776 KB
testcase_06	AC	994 ms 50,808 KB
testcase_07	AC	349 ms 50,776 KB
testcase_08	AC	1,003 ms 50,908 KB
testcase_09	AC	247 ms 50,068 KB
testcase_10	AC	304 ms 50,000 KB
testcase_11	AC	195 ms 49,988 KB
testcase_12	AC	302 ms 58,972 KB
testcase_13	AC	259 ms 54,616 KB
testcase_14	AC	117 ms 54,748 KB
testcase_15	AC	178 ms 53,468 KB
testcase_16	AC	443 ms 56,252 KB
testcase_17	AC	1,068 ms 50,896 KB
testcase_18	AC	1,046 ms 50,772 KB
testcase_19	AC	1,147 ms 52,688 KB
testcase_20	AC	1,116 ms 52,688 KB
testcase_21	AC	1,124 ms 51,860 KB
testcase_22	AC	1,113 ms 52,112 KB
testcase_23	AC	1,116 ms 51,916 KB
testcase_24	AC	1,091 ms 51,660 KB
testcase_25	AC	1,115 ms 53,052 KB
testcase_26	AC	927 ms 60,512 KB
testcase_27	AC	657 ms 57,564 KB
testcase_28	AC	631 ms 57,688 KB
testcase_29	AC	456 ms 55,900 KB
testcase_30	AC	291 ms 54,624 KB
testcase_31	AC	167 ms 53,212 KB
testcase_32	AC	167 ms 53,272 KB
testcase_33	AC	173 ms 53,468 KB
testcase_34	AC	589 ms 57,312 KB
testcase_35	AC	845 ms 58,968 KB
testcase_36	AC	1,109 ms 50,880 KB
testcase_37	AC	1,075 ms 50,508 KB
testcase_38	AC	1,063 ms 50,800 KB
testcase_39	AC	1,083 ms 51,072 KB
testcase_40	AC	1,100 ms 51,664 KB
testcase_41	AC	100 ms 53,472 KB
testcase_42	AC	164 ms 53,216 KB
testcase_43	AC	100 ms 53,336 KB
testcase_44	AC	464 ms 56,156 KB
testcase_45	AC	466 ms 56,160 KB
testcase_46	AC	592 ms 57,432 KB
testcase_47	AC	598 ms 57,692 KB
testcase_48	AC	1,034 ms 49,728 KB
testcase_49	AC	173 ms 53,344 KB
testcase_50	AC	313 ms 54,880 KB
testcase_51	AC	452 ms 56,152 KB
testcase_52	AC	292 ms 50,752 KB

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

ソースコード

raw source code


#include <vector>
#include <utility>

namespace nachia{
    
struct AdjacencyList{
public:
    struct AdjacencyListRange{
        using iterator = typename std::vector<int>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const int& operator[](int i) const { return begi[i]; }
    };
private:
    int mn;
    std::vector<int> E;
    std::vector<int> I;
public:
    AdjacencyList(int n, std::vector<std::pair<int,int>> edges, bool rev){
        mn = n;
        std::vector<int> buf(n+1, 0);
        for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        E.resize(buf[n]);
        for(int i=(int)edges.size()-1; i>=0; i--){
            auto [u,v] = edges[i];
            E[--buf[u]] = v;
            if(rev) E[--buf[v]] = u;
        }
        I = std::move(buf);
    }
    AdjacencyList(const std::vector<std::vector<int>>& edges = {}){
        int n = mn = edges.size();
        std::vector<int> buf(n+1, 0);
        for(int i=0; i<n; i++) buf[i+1] = buf[i] + edges[i].size();
        E.resize(buf[n]);
        for(int i=0; i<n; i++) for(int j=0; j<(int)edges[i].size(); j++) E[buf[i]+j] = edges[i][j];
        I = std::move(buf);
    }
    AdjacencyListRange operator[](int u) const {
        return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] };
    }
    int num_vertices() const { return mn; }
    int num_edges() const { return E.size(); }
    AdjacencyList reversed_edges() const {
        AdjacencyList res;
        int n = res.mn = mn;
        std::vector<int> buf(n+1, 0);
        for(int v : E) ++buf[v];
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.E.resize(buf[n]);
        for(int u=0; u<n; u++) for(int v : operator[](u)) res.E[--buf[v]] = u;
        res.I = std::move(buf);
        return res;
    }
};

struct AdjacencyListEdgeIndexed{
public:
    struct Edge { int to; int edgeidx; };
    struct AdjacencyListRange{
        using iterator = typename std::vector<Edge>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const Edge& operator[](int i) const { return begi[i]; }
    };
private:
    int mn;
    std::vector<Edge> E;
    std::vector<int> I;
public:
    AdjacencyListEdgeIndexed(int n, const std::vector<std::pair<int,int>>& edges, bool rev){
        mn = n;
        std::vector<int> buf(n+1, 0);
        for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        E.resize(buf[n]);
        for(int i=(int)edges.size()-1; i>=0; i--){
            auto [u,v] = edges[i];
            E[--buf[u]] = { v, i };
            if(rev) E[--buf[v]] = { u, i };
        }
        I = std::move(buf);
    }
    AdjacencyListEdgeIndexed() : AdjacencyListEdgeIndexed(0, {}, false) {}
    AdjacencyListRange operator[](int u) const {
        return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] };
    }
    int num_vertices() const { return mn; }
    int num_edges() const { return E.size(); }
    AdjacencyListEdgeIndexed reversed_edges() const {
        AdjacencyListEdgeIndexed res;
        int n = res.mn = mn;
        std::vector<int> buf(n+1, 0);
        for(auto [v,i] : E) ++buf[v];
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.E.resize(buf[n]);
        for(int u=0; u<n; u++) for(auto [v,i] : operator[](u)) res.E[--buf[v]] = {u,i};
        res.I = std::move(buf);
        return res;
    }
};

} // namespace nachia

#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<class T>
using nega_queue = priority_queue<T,vector<T>,greater<T>>;

const int INF = 1001001001;

const int W = 600;
const int H = 600;
const int NV = W * H; // number of vertices
const int maxV = 7;

struct Start{ int id,v; };

int pos2id(int y,int x){ return y * W + x; }

int X,Y;
int N;
vector<Start> hikyaku;
double dt[maxV];
double V[maxV];
double T[maxV][NV];
nachia::AdjacencyList E;

double D[maxV][NV];

int main(){
  cin >> X >> Y; X--; Y--;
  cin >> N;

  {
    vector<pair<int,int>> edges;
    rep(y,H) rep(x,W-1) edges.push_back({ pos2id(y,x), pos2id(y,x+1) });
    rep(y,H-1) rep(x,W) edges.push_back({ pos2id(y,x), pos2id(y+1,x) });
    E = nachia::AdjacencyList(NV, edges, true);
  }

  hikyaku.resize(N);
  rep(i,N){
    int x,y,v; cin >> x >> y >> v;
    x--; y--; v--;
    hikyaku[i] = { pos2id(y,x),v };
  }

  rep(v,maxV) V[v] = 1+v;
  rep(v,maxV) dt[v] = 1000.0 / (1+v);
  
  rep(v,maxV) rep(i,NV) T[v][i] = INF;

  {
    vector<vector<int>> I(maxV);
    for(auto a : hikyaku){
      I[a.v].push_back(a.id);
      T[a.v][a.id] = 0;
    }
    rep(v,maxV){
      rep(i,I[v].size()){
        int p = I[v][i];
        for(int e : E[p]) if(T[v][e] >= INF - 1.0){
          T[v][e] = T[v][p] + dt[v];
          I[v].push_back(e);
        }
      }
    }
  }
  
  rep(v,maxV) rep(i,NV) D[v][i] = INF;

  nega_queue<pair<double,pair<int,int>>> Q;
  D[hikyaku[0].v][hikyaku[0].id] = 0.0;
  Q.push(make_pair(0.0,make_pair(hikyaku[0].v,hikyaku[0].id)));

  while(Q.size()){
    double d = Q.top().first;
    int v = Q.top().second.first;
    int p = Q.top().second.second;
    Q.pop();
    if(D[v][p] != d) continue;
    for(int nxv=v+1; nxv<maxV; nxv++) if(D[nxv][p] > max(T[nxv][p],d)){
      D[nxv][p] = max(T[nxv][p],d);
      Q.push(make_pair(D[nxv][p],make_pair(nxv,p)));
    }
    for(int e : E[p]){
      if(D[v][e] > d + dt[v]){
        D[v][e] = d + dt[v];
        Q.push(make_pair(D[v][e],make_pair(v,e)));
      }
      double nxd = dt[v];
      int pv = v;
      for(int nxv=v+1; nxv<maxV; nxv++){
        double t0 = d + nxd - max(d - dt[nxv], T[nxv][e]);
        if(t0 < 0) continue;
        t0 = min(t0,dt[pv]+dt[nxv]);
        double t = nxd - t0 * (V[nxv] - V[pv]) / (V[nxv] + V[pv]);
        nxd = t; pv = nxv;
        if(D[nxv][e] <= d+nxd) continue;
        D[nxv][e] = d+nxd;
        Q.push(make_pair(d+nxd,make_pair(nxv,e)));
      }
    }
  }

  double ans = INF;
  rep(v,maxV) ans = min(ans,D[v][pos2id(Y,X)]);
  cout.precision(10); cout << fixed;
  cout << ans << endl;
  return 0;
}

struct ios_do_not_sync{
  ios_do_not_sync(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} ios_do_not_sync_inst;

yukicoder

結果

テストケース

ソースコード