結果

問題 No.1308 ジャンプビーコン
ユーザー 👑 jupirojupiro
提出日時 2020-12-05 19:16:46
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 3,771 ms / 4,000 ms
コード長 6,159 bytes
コンパイル時間 2,097 ms
コンパイル使用メモリ 163,056 KB
実行使用メモリ 266,852 KB
最終ジャッジ日時 2023-10-14 01:29:03
合計ジャッジ時間 47,464 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 2 ms
4,352 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,352 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 1 ms
4,352 KB
testcase_08 AC 4 ms
4,348 KB
testcase_09 AC 3 ms
4,348 KB
testcase_10 AC 3 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 3 ms
4,352 KB
testcase_13 AC 137 ms
15,872 KB
testcase_14 AC 99 ms
15,956 KB
testcase_15 AC 91 ms
15,776 KB
testcase_16 AC 53 ms
15,960 KB
testcase_17 AC 49 ms
15,784 KB
testcase_18 AC 2,909 ms
266,568 KB
testcase_19 AC 3,004 ms
266,852 KB
testcase_20 AC 1,862 ms
266,572 KB
testcase_21 AC 1,586 ms
266,568 KB
testcase_22 AC 1,581 ms
266,672 KB
testcase_23 AC 1 ms
4,352 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 AC 2 ms
4,352 KB
testcase_26 AC 1,268 ms
266,588 KB
testcase_27 AC 1,208 ms
266,588 KB
testcase_28 AC 1,199 ms
266,632 KB
testcase_29 AC 3,067 ms
266,672 KB
testcase_30 AC 2,992 ms
266,712 KB
testcase_31 AC 3,771 ms
266,656 KB
testcase_32 AC 2,875 ms
266,696 KB
testcase_33 AC 2,886 ms
266,672 KB
testcase_34 AC 1,615 ms
266,636 KB
testcase_35 AC 1,527 ms
266,600 KB
testcase_36 AC 1,861 ms
266,600 KB
testcase_37 AC 1,923 ms
266,652 KB
testcase_38 AC 2,922 ms
266,600 KB
testcase_39 AC 2,978 ms
266,652 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;
using ull = unsigned long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); }return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long  mod = 998244353;


struct HLD {
	vector<int> sz, in, out, head, par;
	vector<vector<int>> g;
	HLD() {}
	HLD(vector<vector<int>>& _g) : g(_g), sz(_g.size()), in(_g.size()), out(_g.size()), head(_g.size()), par(_g.size()) { build(); }
	void dfs_sz(int cur, int pre) {
		sz[cur] = 1;
		for (int& next : g[cur]) {
			if (next == pre) continue;
			dfs_sz(next, cur);
			par[next] = cur;
			sz[cur] += sz[next];
			if (sz[next] > sz[g[cur][0]]) swap(next, g[cur][0]);
		}
	}

	void dfs_hld(int cur, int pre, int& idx) {
		in[cur] = idx++;
		for (int& next : g[cur]) {
			if (next == pre) continue;
			if (next == g[cur][0]) head[next] = head[cur];
			else head[next] = next;
			dfs_hld(next, cur, idx);
		}
		out[cur] = idx;
	}

	void build() {
		dfs_sz(0, -1);
		int idx = 0;
		dfs_hld(0, -1, idx);
	}

	void build(vector<vector<int>>& _g) {
		g = _g;
		sz.resize(g.size());
		in.resize(g.size());
		out.resize(g.size());
		head.resize(g.size());
		par.resize(g.size());

		dfs_sz(0, -1);
		int idx = 0;
		dfs_hld(0, -1, idx);
	}
	int lca(int u, int v) {
		for (;; v = par[head[v]]) {
			if (in[u] > in[v]) swap(u, v);
			if (head[u] == head[v]) return u;
		}
	}

	//[l, r)の区間集合を返す
	vector<pair<int, int>> path_query(int u, int v, bool edge = false) {
		vector<pair<int, int>> ret;
		for (;; v = par[head[v]]) {
			if (in[u] > in[v]) swap(u, v);
			if (head[u] == head[v]) break;
			ret.emplace_back(in[head[v]], in[v] + 1);
		}
		ret.emplace_back(in[u] + edge, in[v] + 1);
		return ret;
	}
};

template< typename OperatorMonoid, typename H >
struct DualSegmentTree {
    int sz, height;
    vector< OperatorMonoid > lazy;
    const H h;
    const OperatorMonoid OM0;

    DualSegmentTree(int n, const H h, const OperatorMonoid& OM0) : h(h), OM0(OM0) {
        sz = 1;
        height = 0;
        while (sz < n) sz <<= 1, height++;
        lazy.assign(2 * sz, OM0);
    }

    inline void propagate(int k) {
        if (lazy[k] != OM0) {
            lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
            lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
            lazy[k] = OM0;
        }
    }

    inline void thrust(int k) {
        for (int i = height; i > 0; i--) propagate(k >> i);
    }

    void update(int a, int b, const OperatorMonoid& x) {
        thrust(a += sz);
        thrust(b += sz - 1);
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lazy[l] = h(lazy[l], x), ++l;
            if (r & 1) --r, lazy[r] = h(lazy[r], x);
        }
    }

    OperatorMonoid operator[](int k) {
        thrust(k += sz);
        return lazy[k];
    }
};

template< typename OperatorMonoid, typename H >
DualSegmentTree< OperatorMonoid, H > get_dual_segment_tree(int N, const H& h, const OperatorMonoid& OM0) {
    return { N, h, OM0 };
}

struct Edge {
    int from, to;
    ll cost;
    Edge(int from, int to, ll cost) :from(from), to(to), cost(cost) {}
};

vector<ll> bfs(int st, vector<vector<pair<int, ll>>>& g) {
    int n = g.size();
    vector<ll> d(n, INF);
    d[st] = 0;
    queue<int> q; q.emplace(st);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto [nxt, len] : g[cur]) {
            if (chmin(d[nxt], d[cur] + len)) {
                q.emplace(nxt);
            }
        }
    }
    return d;
}
int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n, kkt; cin >> n >> kkt;
	ll C; cin >> C;
    vector<Edge> edges; edges.reserve(n - 1);
    vector<vector<int>> g(n);
    vector<vector<pair<int, ll>>> tg(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, l; cin >> u >> v >> l;
        u--; v--;
        edges.emplace_back(u, v, l);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        tg[u].emplace_back(v, l);
        tg[v].emplace_back(u, l);
    }

    vector<vector<ll>> dist(n); for (int i = 0; i < n; i++) dist[i] = bfs(i, tg);

    HLD hld(g);

    auto f1 = [](ll a, ll b) {return min(a, b); };
    auto f2 = [](ll a, ll b) {
        return min(a, b);
    };
    auto lsg = get_dual_segment_tree(n, f2, INF);
    vector d(kkt, lsg);
    vector<int> x(kkt); for (int i = 0; i < kkt; i++) cin >> x[i], x[i]--;
    d[0].update(hld.in[x[0]], hld.in[x[0]] + 1, 0);
    for (int jupi = 1; jupi < kkt; jupi++) {
        int cur = x[jupi];
        int pre = x[jupi - 1];
        ll p = INF;
        for (int j = 0; j < n; j++) {
            chmin(p, d[jupi - 1][j]);
        }
        for (auto [l, r] : hld.path_query(pre, cur)) {
            d[jupi].update(l, r, p + dist[pre][cur]);
        }
        for (int j = 0; j < n; j++) {
            ll t = dist[pre][cur];
            ll p = d[jupi - 1][hld.in[j]];
            if (p == INF) continue;
            d[jupi].update(hld.in[j], hld.in[j] + 1, p + t);

            if (C + dist[j][cur] < t) {
                for (auto [l, r] : hld.path_query(j, cur)) {
                    d[jupi].update(l, r, p + C + dist[j][cur]);
                }
            }
        }
    }
    ll res = INF; for (int i = 0; i < n; i++) chmin(res, d.back()[i]);
    cout << res << "\n";
}
0