結果

問題 No.1995 CHIKA Road
ユーザー log_Klog_K
提出日時 2023-07-12 09:46:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 472 ms / 2,000 ms
コード長 14,292 bytes
コンパイル時間 2,797 ms
コンパイル使用メモリ 233,180 KB
実行使用メモリ 46,044 KB
最終ジャッジ日時 2023-10-11 23:50:30
合計ジャッジ時間 13,278 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 18 ms
5,720 KB
testcase_07 AC 71 ms
11,428 KB
testcase_08 AC 2 ms
4,352 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 98 ms
14,184 KB
testcase_11 AC 472 ms
46,044 KB
testcase_12 AC 256 ms
28,612 KB
testcase_13 AC 121 ms
17,300 KB
testcase_14 AC 130 ms
17,576 KB
testcase_15 AC 413 ms
43,404 KB
testcase_16 AC 31 ms
7,184 KB
testcase_17 AC 169 ms
22,880 KB
testcase_18 AC 311 ms
31,828 KB
testcase_19 AC 312 ms
32,280 KB
testcase_20 AC 151 ms
19,152 KB
testcase_21 AC 137 ms
17,616 KB
testcase_22 AC 299 ms
30,444 KB
testcase_23 AC 73 ms
12,856 KB
testcase_24 AC 250 ms
28,020 KB
testcase_25 AC 39 ms
8,348 KB
testcase_26 AC 90 ms
15,184 KB
testcase_27 AC 242 ms
26,800 KB
testcase_28 AC 134 ms
17,684 KB
testcase_29 AC 305 ms
30,772 KB
testcase_30 AC 37 ms
8,512 KB
testcase_31 AC 18 ms
5,528 KB
testcase_32 AC 51 ms
9,560 KB
testcase_33 AC 233 ms
26,732 KB
testcase_34 AC 20 ms
5,888 KB
testcase_35 AC 82 ms
14,792 KB
testcase_36 AC 100 ms
14,356 KB
testcase_37 AC 278 ms
29,608 KB
testcase_38 AC 185 ms
23,832 KB
testcase_39 AC 16 ms
5,492 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "yuki-1995.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1995"

#line 2 "/mnt/c/Users/koji0/Desktop/Procon/library/Template.hpp"

/**
 * @brief Procon Template - テンプレート
 */

#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort(RALL(x))
#define REVERSE(x) reverse(ALL(x))
#define SETPRE(digit) fixed << setprecision(digit)
#define popcount(x) __builtin_popcount(x)
#define ACC(x) accumulate((x).begin(), (x).end(), 0LL)
using namespace std;

#ifndef ONLINE_JUDGE
void dprint(){
    cerr << endl;
}
template<class Head, class... Tail>
void dprint(Head&& head, Tail&&... tail){
    cerr << head << " ";
    dprint(forward<Tail>(tail)...);
}
#else
template<class Head, class... Tail>
void dprint(Head&& head, Tail&&... tail){}
#endif

inline string Yn(bool flag){return (flag) ? "Yes" : "No";}
inline bool YnPrint(bool flag){cout << Yn(flag) << endl;return flag;}
inline string YN(bool flag){return (flag) ? "YES" : "NO";}
inline bool YNPrint(bool flag){cout << YN(flag) << endl;return flag;}
template<class T>
bool minin(T &src, const T &cmp){if(src > cmp){src = cmp; return true;}return false;}
template<class T>
bool maxin(T &src, const T &cmp){if(src < cmp){src = cmp; return true;}return false;}
template<typename T>
inline bool between(T min, T x, T max){return min <= x && x <= max;}
template<typename T>
inline T median(T a, T b, T c){return between(b, a, c) || between(c, a, b) ? a : (between(a, b, c) || between(c, b, a) ? b : c);}

using ll = long long;
using ull = unsigned long long;
using ld = long double;

const long double PI = acosl(-1);
const long double PI2 = PI * 2;
const long double PI_2 = PI / 2;

const int INF_INT = numeric_limits<int>::max() / 2;
const long long INF_LL = numeric_limits<long long>::max() / 2LL;

template <typename T>
using vec = vector<T>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using rpq = priority_queue<T, vec<T>, greater<T>>;

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, -1, 0, 1};
const int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy8[8] = {0, -1, -1, -1, 0, 1, 1, 1};

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p){
    os << "{" << p.first << " " << p.second << "}";
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p){
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v){
    for (int i = 0; i < v.size(); ++i){
        os << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &v){
    for (int i = 0; i < v.size(); ++i){
        os << v[i] << "\n";
    }
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (int i = 0; i < v.size(); ++i) is >> v[i];
    return is;
}

template <typename T>
istream &operator>>(istream &is, valarray<T> &v){
    for (int i = 0; i < v.size(); ++i) is >> v[i];
    return is;
}

template <typename T1, typename T2, typename T3>
pair<T1, T2> &operator+=(pair<T1, T2> &x, const T3 &y){
    x.first += y;
    x.second += y;
    return x;
}

template <typename T1, typename T2, typename T3>
pair<T1, T2> &operator-=(pair<T1, T2> &x, const T3 &y){
    x.first -= y;
    x.second -= y;
    return x;
}

ll modpow(ll a, ll b, ll m){
    ll p = 1, q = a;
    for (int i = 0; i < 63; ++i)
    {
        if ((b & (1LL << i)) != 0)
        {
            p *= q;
            p %= m;
        }
        q *= q;
        q %= m;
    }
    return p;
}

template <typename T>
inline long long EuclideanDist2(const pair<T, T> &p1, const pair<T, T> &p2){
    long long dx = (long long)p1.first - (long long)p2.first;
    long long dy = (long long)p1.second - (long long)p2.second;
    return dx * dx + dy * dy;
}

template <typename T>
inline long long EuclideanDist2(const pair<T, T> &p){
    return EuclideanDist2(p, make_pair(0, 0));
}

template <typename T>
inline double EuclideanDist(const pair<T, T> &p1, const pair<T, T> &p2){
    return sqrt((double)EuclideanDist2(p1, p2));
}

template <typename T>
inline double EuclideanDist(const pair<T, T> &p){
    return sqrt((double)EuclideanDist2(p));
}

template<typename T>
inline long long ManhattanDist(const pair<T, T> &p1, const pair<T, T> &p2){
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

template <typename T>
T ceil(T x, T y){
    return (x + y - 1) / y;
}

template<typename T>
T gcd(T a, T b) {
    if(a < 0) a = -a;
    if(b < 0) b = -b;
    if(b == 0) return a;
    else return gcd(b, a % b);
}

ull lcm(ull a, ull b) {
    return a * b / gcd(a, b);
}

string bitseq(long long x){
    string ret = "";
    while(x){
        ret.push_back('0' + (x & 1));
        x <<= 1;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
#line 4 "yuki-1995.test.cpp"

#line 2 "/mnt/c/Users/koji0/Desktop/Procon/library/Compress.hpp"

/**
 * @brief Compress - 座標圧縮
 */

#line 10 "/mnt/c/Users/koji0/Desktop/Procon/library/Compress.hpp"
using namespace std;

struct Compress{
    int sz;
    vector<int> to_val;
    map<int, int> to_index;

    /**
     * @brief  配列Vで構築する。
     */
    Compress(vector<int> &V){
        for(auto &v : V){
            to_val.emplace_back(v);
        }
        sort(to_val.begin(), to_val.end());
        auto border = unique(to_val.begin(), to_val.end());
        to_val.erase(border, to_val.end());
        sz = to_val.size();
        for(int i = 0; i < sz; ++i){
            to_index[to_val[i]] = i;
        }
    }

    // 値を対応するインデックスに
    inline int vi(int value){
        return to_index[value];
    }

    // インデックスを対応する値に
    inline int iv(int index){
        return to_val[index];
    }
};
#line 2 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/GraphTemplate.hpp"

/**
 * @brief Graph Template - グラフテンプレート
 */

#line 8 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/GraphTemplate.hpp"
using namespace std;

using EdgeNum = int;
using Vertex = int;

/**
 * @brief グラフの辺
 */
template<typename CostType = int>
struct Edge{
    Vertex from, to;
    CostType cost;

    Edge(Vertex from, Vertex to, CostType cost) : from(from), to(to), cost(cost){}
};

/**
 * @brief グラフを表すクラス。
 * @note 辺集合によって実現している。
 * @tparam CostType 辺の重みの型。
 */
template<typename CostType = int>
class Graph{
    private:
    int sz;
    bool dir;
    vector<int> indegree;

    public:
    vector<Edge<CostType>> edges;
    vector<vector<EdgeNum>> connect;
    vector<EdgeNum> rev; // 形式上無向グラフでも有向辺を追加するので、辺の追加時に逆辺の辺番号を記録できるようにする
    CostType INF;

    /**
     * @brief Construct a new Graph object
     * @param VertexNum グラフの頂点数
     * @param isDirected 有向グラフとして作成するか
     */
    Graph(int VertexNum, bool isDirected = false) : sz(VertexNum), dir(isDirected), connect(VertexNum), indegree(VertexNum), INF(numeric_limits<CostType>::max()){}

    Graph() = default;

    /**
     * @brief グラフに頂点sと頂点t間の辺を追加する。
     * @note 有向グラフならば頂点sから頂点tへの有向辺を、無向グラフならば頂点sと頂点tを結ぶ無向辺を追加する。
     * @param s 頂点s
     * @param t 頂点t
     * @param w 辺の重み (option, default = 1)
     */
    void add(Vertex s, Vertex t, CostType w = 1){
        assert(0 <= s && s < sz);
        assert(0 <= t && t < sz);
        EdgeNum e = edges.size();
        edges.push_back(Edge<CostType>(s, t, w));
        connect[s].push_back(e);
        ++indegree[t];
        if(!dir){
            edges.push_back(Edge<CostType>(t, s, w));
            connect[t].push_back(e + 1);
            rev.emplace_back(e + 1);
            rev.emplace_back(e);
        }
    }

    /**
     * @brief 指定した辺番号の辺を取得する。
     * @param idx 辺番号
     * @return Edge<CostType> 辺情報
     */
    Edge<CostType> get_edge(EdgeNum idx){
        int e = edges.size();
        assert(0 <= idx && idx < e);
        return edges[idx];
    }

    /**
     * @brief 指定した頂点番号に接続する辺の一覧を取得する。
     * @param v 頂点番号
     * @return vector<Edge<CostType>> 指定した頂点番号に接続する辺の一覧
     */
    vector<Edge<CostType>> get_edges(Vertex v){
        assert(0 <= v && v < sz);
        vector<Edge<CostType>> ret;
        for(auto &idx : connect[v]) ret.push_back(get_edge(idx));
        return ret;
    }

    /**
     * @brief 指定した頂点番号に接続する辺番号の一覧を取得する。
     * @param v 頂点番号
     * @return vector<EdgeNum> 指定した頂点番号に接続する辺番号の一覧
     */
    vector<EdgeNum> get_list(Vertex v){
        assert(0 <= v && v < sz);
        return connect[v];
    }

    /**
     * @brief 逆辺を張ったグラフを作成する。
     * @attention この操作は有向グラフにのみ可能である。
     * @return Graph<CostType> 逆辺を張ったグラフ
     */
    Graph<CostType> reverse(){
        assert(dir);
        Graph<CostType> ret(sz, true);
        for(auto &e : edges){
            ret.add(e.to, e.from, e.cost);
        }
        return ret;
    }

    inline size_t size(){
        return sz;
    }

    inline bool directed(){
        return dir;
    }

    /**
     * @brief ある頂点の次数(出次数)を取得する。
     * @note 有向グラフにおいて、第2引数をtrueにすれば入次数を得ることができる。
     * @param v 頂点番号
     * @param isIn (有向グラフのときのみ有効)入次数を取得するか (option, default = false)
     * @return int 頂点vの指定した値
     */
    inline int degree(Vertex v, bool isIn = false){
        if(dir && isIn) return indegree[v];
        return (int)connect[v].size();
    }

    /**
     * @brief グラフを頂点rootを根とした無向根付き木とみなしたとき、各頂点の親頂点の番号と、それを結ぶ辺番号を取得する。
     * @attention グラフが無向木でない場合の動作は未定義である。
     * @param root 木の根とする頂点番号
     * @return vector<pair<Vertex, EdgeNum>> 各頂点の親の頂点番号と親への辺番号（頂点rootに対してはどちらも-1とする）
     */
    vector<pair<Vertex, EdgeNum>> get_parent(Vertex root){
        vector<pair<Vertex, EdgeNum>> ret(sz, pair<Vertex, EdgeNum>(-1, -1));
        stack<pair<Vertex, Vertex>> st;
        st.emplace(root, -1);
        while(!st.empty()){
            auto [v, parent] = st.top();
            st.pop();
            for(auto &idx : connect[v]){
                if(edges[idx].to == parent) continue;
                ret[edges[idx].to] = pair<Vertex, EdgeNum>(v, rev[idx]);
                st.emplace(edges[idx].to, v);
            }
        }
        return ret;
    }
};
#line 2 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/Dijkstra.hpp"

/**
 * @brief Dijkstra - 単一始点最短距離（ダイクストラ法）
 */

#line 9 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/Dijkstra.hpp"
using namespace std;

/**
 * @brief  ダイクストラ法で最短距離を求める。
 * @attention グラフに負の重みの辺がない必要がある。
 */
template<typename CostType>
struct Dijkstra{
    private:
    Graph<CostType> &G;
    vector<Vertex> prev_vertex;
    vector<EdgeNum> prev_edge;

    public:
    vector<CostType> dist;

    Dijkstra(Graph<CostType> &G) : G(G), dist(G.size()), prev_vertex(G.size()), prev_edge(G.size()){}

    /**
     * @brief  頂点sを始点としてダイクストラ法を適用する。
     * @param  s: 始点となる頂点s
     * @note   求められた最短距離はdistに格納される。
     */
    void build(int s){
        dist.assign(G.size(), G.INF);
        prev_vertex.assign(G.size(), -1);
        prev_edge.assign(G.size(), -1);
        using p = pair<CostType, Vertex>;
        priority_queue<p, vector<p>, greater<p>> que;
        que.emplace(0, s);
        dist[s] = 0;
        while(!que.empty()){
            auto [d, v] = que.top();
            que.pop();
            if(dist[v] < d) continue;
            for(auto &eidx : G.get_list(v)){
                auto e = G.get_edge(eidx);
                if(d + e.cost < dist[e.to]){
                    dist[e.to] = d + e.cost;
                    prev_vertex[e.to] = v;
                    prev_edge[e.to] = eidx;
                    que.emplace(d + e.cost, e.to);
                }
            }
        }
    }

    /**
     * @brief  頂点sから頂点tへの最短経路を取得する
     * @attention 予めbuildで最短距離を求める必要がある。
     * @param  t: 終点となる頂点t
     * @param  isEdge: 頂点番号の代わりに辺番号を取得する(opt default = false)
     * @retval 最短経路の頂点番号 or 辺番号
     */
    vector<int> restore(int t, bool isEdge = false){
        vector<int> ret;
        int v = t;
        while(v != -1){
            if(!isEdge) ret.push_back(v);
            else if(prev_edge[v] != -1) ret.push_back(prev_edge[v]);
            v = prev_vertex[v];
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
#line 8 "yuki-1995.test.cpp"

int main(){
    int N, M;
    cin >> N >> M;
    vector<long long> A(M), B(M);
    vector<int> city{1, N};
    for(int i = 0; i < M; ++i){
        cin >> A[i] >> B[i];
        city.emplace_back(A[i]);
        city.emplace_back(B[i]);
    }
    Compress cp(city);
    Graph<long long> G(cp.sz);
    for(int i = 0; i < cp.sz - 1; ++i){
        G.add(i, i + 1, (cp.iv(i + 1) - cp.iv(i)) * 2LL);
    }
    for(int i = 0; i < M; ++i){
        G.add(cp.vi(A[i]), cp.vi(B[i]), 2 * B[i] - 2 * A[i] - 1);
    }
    Dijkstra dk(G);
    dk.build(0);
    cout << dk.dist[cp.sz - 1] << endl;
}
0