結果

問題 No.1308 ジャンプビーコン
ユーザー jupirojupiro
提出日時 2020-12-05 19:00:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,602 bytes
コンパイル時間 2,278 ms
コンパイル使用メモリ 165,364 KB
実行使用メモリ 464,000 KB
最終ジャッジ日時 2024-09-15 20:39:29
合計ジャッジ時間 11,847 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 8 ms
5,376 KB
testcase_11 AC 8 ms
5,376 KB
testcase_12 AC 8 ms
5,376 KB
testcase_13 AC 749 ms
27,904 KB
testcase_14 AC 726 ms
27,904 KB
testcase_15 AC 748 ms
27,904 KB
testcase_16 AC 697 ms
27,776 KB
testcase_17 AC 720 ms
27,776 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

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 Monoid, typename OperatorMonoid, typename F, typename G, typename H >
struct LazySegmentTree {
    int sz, height;
    vector< Monoid > data;
    vector< OperatorMonoid > lazy;
    const F f;
    const G g;
    const H h;
    const Monoid M1;
    const OperatorMonoid OM0;

    LazySegmentTree(int n, const F f, const G g, const H h,
        const Monoid& M1, const OperatorMonoid OM0)
        : f(f), g(g), h(h), M1(M1), OM0(OM0) {
        sz = 1;
        height = 0;
        while (sz < n) sz <<= 1, height++;
        data.assign(2 * sz, M1);
        lazy.assign(2 * sz, OM0);
    }

    void set(int k, const Monoid& x) {
        data[k + sz] = x;
    }

    void build() {
        for (int k = sz - 1; k > 0; k--) {
            data[k] = f(data[2 * k + 0], data[2 * k + 1]);
        }
    }

    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]);
            data[k] = apply(k);
            lazy[k] = OM0;
        }
    }

    inline Monoid apply(int k) {
        return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
    }

    inline void recalc(int k) {
        while (k >>= 1) data[k] = f(apply(2 * k + 0), apply(2 * k + 1));
    }

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

    void update(int a, int b, const OperatorMonoid& x) {
        if (a >= b) return;
        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);
        }
        recalc(a);
        recalc(b);
    }

    Monoid query(int a, int b) {
        if (a >= b) return M1;
        thrust(a += sz);
        thrust(b += sz - 1);
        Monoid L = M1, R = M1;
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = f(L, apply(l++));
            if (r & 1) R = f(apply(--r), R);
        }
        return f(L, R);
    }

    Monoid operator[](const int& k) {
        return query(k, k + 1);
    }

    template< typename C >
    int find_subtree(int a, const C& check, Monoid& M, bool type) {
        while (a < sz) {
            propagate(a);
            Monoid nxt = type ? f(apply(2 * a + type), M) : f(M, apply(2 * a + type));
            if (check(nxt)) a = 2 * a + type;
            else M = nxt, a = 2 * a + 1 - type;
        }
        return a - sz;
    }

    template< typename C >
    int find_first(int a, const C& check) {
        Monoid L = M1;
        if (a <= 0) {
            if (check(f(L, apply(1)))) return find_subtree(1, check, L, false);
            return -1;
        }
        thrust(a + sz);
        int b = sz;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) {
                Monoid nxt = f(L, apply(a));
                if (check(nxt)) return find_subtree(a, check, L, false);
                L = nxt;
                ++a;
            }
        }
        return -1;
    }

    template< typename C >
    int find_last(int b, const C& check) {
        Monoid R = M1;
        if (b >= sz) {
            if (check(f(apply(1), R))) return find_subtree(1, check, R, true);
            return -1;
        }
        thrust(b + sz - 1);
        int a = sz;
        for (b += sz; a < b; a >>= 1, b >>= 1) {
            if (b & 1) {
                Monoid nxt = f(apply(--b), R);
                if (check(nxt)) return find_subtree(b, check, R, true);
                R = nxt;
            }
        }
        return -1;
    }
};

template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >
LazySegmentTree< Monoid, OperatorMonoid, F, G, H > get_lazy_segment_tree
(int N, const F& f, const G& g, const H& h, const Monoid& M1, const OperatorMonoid& OM0) {
    return { N, f, g, h, M1, 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_lazy_segment_tree(n, f1, f2, f2, INF, 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];
        
        for (int j = 0; j < n; j++) {
            ll t = dist[pre][cur];
            ll p = d[jupi - 1].query(hld.in[j], hld.in[j] + 1);
            d[jupi].update(hld.in[j], hld.in[j] + 1, p + t);
            for (auto [l, r] : hld.path_query(pre, cur)) {
                d[jupi].update(l, r, p + t);
            }
            for (auto [l, r] : hld.path_query(j, cur)) {
                d[jupi].update(l, r, p + C + dist[j][cur]);
            }
        }
    }
    cout << d.back().query(0, n) << "\n";
}
0