#589494 (C++17) No.1308 ジャンプビーコン

提出ソース

結果

問題	No.1308 ジャンプビーコン
ユーザー	ningenMe
提出日時	2020-12-05 06:07:56
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	10,864 bytes
コンパイル時間	3,213 ms
コンパイル使用メモリ	234,568 KB
実行使用メモリ	75,528 KB
最終ジャッジ日時	2024-09-15 10:35:31
合計ジャッジ時間	59,513 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	5 ms 5,376 KB
testcase_09	AC	5 ms 5,376 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	AC	5 ms 5,376 KB
testcase_12	AC	4 ms 5,376 KB
testcase_13	AC	178 ms 8,576 KB
testcase_14	AC	174 ms 8,320 KB
testcase_15	AC	185 ms 8,448 KB
testcase_16	AC	180 ms 8,448 KB
testcase_17	AC	172 ms 8,320 KB
testcase_18	AC	3,080 ms 75,300 KB
testcase_19	AC	3,086 ms 75,296 KB
testcase_20	AC	3,117 ms 75,304 KB
testcase_21	AC	3,127 ms 75,428 KB
testcase_22	AC	3,115 ms 75,364 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	4 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	1,742 ms 75,176 KB
testcase_27	AC	1,733 ms 75,176 KB
testcase_28	AC	1,744 ms 75,176 KB
testcase_29	AC	3,837 ms 75,420 KB
testcase_30	AC	3,832 ms 75,528 KB
testcase_31	AC	3,589 ms 75,452 KB
testcase_32	AC	3,613 ms 75,416 KB
testcase_33	TLE	-
testcase_34	AC	1,736 ms 75,048 KB
testcase_35	AC	1,734 ms 75,176 KB
testcase_36	AC	2,139 ms 75,308 KB
testcase_37	AC	2,138 ms 75,304 KB
testcase_38	AC	3,393 ms 75,304 KB
testcase_39	AC	3,415 ms 75,436 KB

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

ソースコード

raw source code

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

#define ALL(obj) (obj).begin(),(obj).end()
template<class T> using priority_queue_reverse = priority_queue<T,vector<T>,greater<T>>;

constexpr long long MOD = 1'000'000'000LL + 7; //'
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433L;

template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
vector<string> split(const string &str, const char delemiter) {vector<string> res;stringstream ss(str);string buffer; while( getline(ss, buffer, delemiter) ) res.push_back(buffer); return res;}
int msb(int x) {return x?31-__builtin_clz(x):-1;}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

/*
 * @title Graph
 * @docs md/graph/Graph.md
 */
template<class T> class Graph{
private:
    const size_t N,H,W;
public:
    vector<vector<pair<size_t,T>>> edges;
    Graph():H(-1),W(-1),N(0) {}
    Graph(const size_t N):H(-1),W(-1),N(N), edges(N) {}
    Graph(const size_t H, const size_t W):H(H),W(W),N(H*W), edges(H*W) {}
    inline void make_edge(size_t from, size_t to, T w) {
        edges[from].emplace_back(to,w);
    }
    //{from_y,from_x} -> {to_y,to_x} 
    inline void make_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) {
        make_edge(from.first*W+from.second,to.first*W+to.second,w);
    }
    inline void make_bidirectional_edge(size_t from, size_t to, T w) {
        make_edge(from,to,w);
        make_edge(to,from,w);
    }
    inline void make_bidirectional_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) {
        make_edge(from.first*W+from.second,to.first*W+to.second,w);
        make_edge(to.first*W+to.second,from.first*W+from.second,w);
    }
    inline void resize(const size_t _N) {N=_N;edges.resize(N);}
    inline size_t size(){return N;}
    inline size_t idx(pair<size_t,size_t> yx){return yx.first*W+yx.second;}
};

template<class Operator> class TreeBuilder;
template<class Operator> class Tree {
    using TypeEdge = typename Operator::TypeEdge;
    size_t num;
    size_t ord;
    Graph<TypeEdge>& g;
    friend TreeBuilder<Operator>;
    /**
     * constructor
     * O(N) 
     */
    Tree(Graph<TypeEdge>& graph):
        g(graph),
        num(graph.size()),
        depth(graph.size(),-1),
        order(graph.size()),
        edge_dist(graph.size()){
    }
	//for make_depth
	void dfs(int curr, int prev){
		for(const auto& e:g.edges[curr]){
			const int& next = e.first;
			if(next==prev) continue;
			depth[next] = depth[curr] + 1;
			edge_dist[next]  = Operator::func_edge_merge(edge_dist[curr],e.second);
			dfs(next,curr);
			order[ord++] = next;
		}
	}
    /**
     * 深さを作る
     * O(N) you can use anytime
     */
	void make_depth(const int root) {
		depth[root] = 0;
		edge_dist[root] = Operator::unit_edge;
		ord = 0;
		dfs(root,-1);
		order[ord++] = root;
		reverse_copy(order.begin(),order.end(),back_inserter(reorder));
	}
	/**
     * 子を作る
     * O(N) after make_depth
     */
	void make_child(const int root = 0) {
		child.resize(num);
		for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] < depth[e.first]) child[i].push_back(e);
	}
	/**
     * 部分木のサイズを作る
     * O(N) after make_depth
     */
	void make_subtree_size() {
		subtree_size.resize(num,1);
		for (size_t i:order) for (auto e : child[i]) subtree_size[i] += subtree_size[e.first];
	}
	/**
     * 親を作る
     * O(N) after make_depth
     */
	void make_parent() {
		parent.resize(num,make_pair(num,Operator::unit_edge));
		for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] > depth[e.first]) parent[i] = e;
	}
	void make_ancestor() {
		ancestor.resize(num);
		for (size_t i = 0; i < num; ++i) ancestor[i][0] = (parent[i].first!=num?parent[i]:make_pair(i,Operator::unit_lca_edge));
		for (size_t j = 1; j < Operator::bit; ++j) {
			for (size_t i = 0; i < num; ++i) {
				size_t k = ancestor[i][j - 1].first;
				ancestor[i][j] = Operator::func_lca_edge_merge(ancestor[k][j - 1],ancestor[i][j - 1]);
			}
		}
	}
    pair<size_t,TypeEdge> lca_impl(size_t l, size_t r) {
		if (depth[l] < depth[r]) swap(l, r);
		int diff = depth[l] - depth[r];
		auto ancl = make_pair(l,Operator::unit_lca_edge);
		auto ancr = make_pair(r,Operator::unit_lca_edge);
		for (int j = 0; j < Operator::bit; ++j) {
			if (diff & (1 << j)) ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl);
		}
		if(ancl.first==ancr.first) return ancl;
		for (int j = Operator::bit - 1; 0 <= j; --j) {
			if(ancestor[ancl.first][j].first!=ancestor[ancr.first][j].first) {
				ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl);
				ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][j],ancr);
			}
		}
		ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][0],ancl);
		ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][0],ancr);
		return Operator::func_lca_edge_merge(ancl,ancr);
    }
public:
	vector<size_t> depth;
	vector<size_t> order;
	vector<size_t> reorder;
    vector<size_t> subtree_size;
    vector<pair<size_t,TypeEdge>> parent;
    vector<vector<pair<size_t,TypeEdge>>> child;
	vector<TypeEdge> edge_dist;
    vector<array<pair<size_t,TypeEdge>,Operator::bit>> ancestor;

    /**
     * O(N) builder
     */
    static TreeBuilder<Operator> builder(Graph<TypeEdge>& graph) {
        return TreeBuilder<Operator>(graph);
    }
    /**
     * O(logN) after make_ancestor
     * return {lca,lca_dist} l and r must be connected 
     */
	pair<size_t,TypeEdge> lca(size_t l, size_t r) {return lca_impl(l,r);}
};

template<class Operator> class TreeBuilder {
    bool is_depth_made =false;
    bool is_child_made =false;
    bool is_parent_made=false;
public:
    using TypeEdge = typename Operator::TypeEdge;
    TreeBuilder(Graph<TypeEdge>& g):tree(g){}
    TreeBuilder& depth(const int root) { is_depth_made=true; tree.make_depth(root); return *this;}
    TreeBuilder& child() { assert(is_depth_made); is_child_made=true;  tree.make_child();  return *this;}
    TreeBuilder& parent() { assert(is_depth_made); is_parent_made=true; tree.make_parent(); return *this;}
    TreeBuilder& subtree_size() { assert(is_child_made); tree.make_subtree_size(); return *this;}
    TreeBuilder& ancestor() { assert(is_parent_made); tree.make_ancestor(); return *this;}
    Tree<Operator>&& build() {return move(tree);}
private:
    Tree<Operator> tree;
};

template<class T> struct TreeOperator{
	using TypeEdge = T;
    inline static constexpr size_t bit = 20;
	inline static constexpr TypeEdge unit_edge = 0;
	inline static constexpr TypeEdge unit_lca_edge = 0;
	inline static constexpr TypeEdge func_edge_merge(const TypeEdge& parent,const TypeEdge& w){return parent+w;}
	inline static constexpr pair<size_t,TypeEdge> func_lca_edge_merge(const pair<size_t,TypeEdge>& l,const pair<size_t,TypeEdge>& r){return make_pair(l.first,l.second+r.second);}
};

/**
 * @url 
 * @est
 */ 
int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    long long N,Q,C; cin >> N >> Q >> C;
    Graph<long long> graph(N);
    for(int i=0;i+1<N;++i) {
        int u,v,w; cin >> u >> v >> w;
        u--,v--;
        graph.make_bidirectional_edge(u,v,w);
    }
    vector<int> X(Q);
    for(int i=0;i<Q;++i) cin >> X[i],X[i]--;

    //dp_i,j := x_iにいて、ジャンプビーコンがjにあるときの最小値。j=Nはビーコンなし。
    auto dp = multivector(Q,N+1,HIGHINF);
    dp[0][N]=0;
    for(int i=1;i<Q;++i) {

        Tree<TreeOperator<long long>> tree 
            = Tree<TreeOperator<long long>>::builder(graph).depth(X[i]).parent().child().ancestor().build();

        //jにあるジャンプビーコンをそのままにして、X[i]へ向かうとき
        for(int j=0;j<=N;++j) {
            chmin(dp[i][j],dp[i-1][j]+tree.edge_dist[X[i-1]]);
        }
        //jにジャンプビーコンを置いて、X[i]へ向かうとき
        for(int j=0;j<N;++j){
            long long cost=0;
            {
                int l=X[i-1],r=j;
                cost += tree.lca(l,r).second;
            }
            {
                int l=j,r=X[i];
                cost += tree.lca(l,r).second;
            }
            chmin(dp[i][j],dp[i-1][N]+cost);
        }
        //ジャンプビーコンを使った後、X[i]へ向かうとき
        for(int j=0;j<N;++j){
            int l=j,r=X[i];
            long long cost = tree.lca(l,r).second;
            chmin(dp[i][N],dp[i-1][j]+cost+C);
        }
        //ジャンプビーコンを使った後jにジャンプビーコンを置いて、X[i]へ向かうとき
        //dp2_j := 頂点jにいるときの最小値
        vector<long long> dp2(N);
        for(int j=0;j<N;++j) dp2[j]=dp[i-1][j]+(X[i-1]==j?0:C);

        for(int j:tree.order) {
            long long cost=0;
            {
                cost+=tree.edge_dist[j];
            }
            for(auto& e:tree.child[j]) {
                int ch = e.first;
                chmin(dp2[j],dp2[ch]+e.second);
            }
            cost += dp2[j];
            chmin(dp[i][j],cost);
        }
    }
    cout << *min_element(ALL(dp.back())) << endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード