結果
問題 | No.1308 ジャンプビーコン |
ユーザー |
![]() |
提出日時 | 2020-12-05 16:07:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,386 ms / 4,000 ms |
コード長 | 4,949 bytes |
コンパイル時間 | 15,936 ms |
コンパイル使用メモリ | 308,988 KB |
最終ジャッジ日時 | 2025-01-16 17:52:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using ll = long long;template <class T> using vec = vector<T>;template <class T> using vvec = vector<vec<T>>;template<class T> bool chmin(T& a,T b){if(a>b) {a = b; return true;} return false;}template<class T> bool chmax(T& a,T b){if(a<b) {a = b; return true;} return false;}#define rep(i,n) for(int i=0;i<(n);i++)#define drep(i,n) for(int i=(n)-1;i>=0;i--)#define all(x) (x).begin(),(x).end()#define debug(x) cerr << #x << " = " << (x) << endl;struct edge{int to,d;};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] = h(lazy[2*k], 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];}};class HeavLightDecomposition{public:vvec<edge> g;vec<int> sz,in,out,head,par;int pos;void dfs_sz(int cur,int p){sz[cur] = 1;par[cur] = p;for(auto& e:g[cur]) if(e.to!=p){dfs_sz(e.to,cur);sz[cur] += sz[e.to];if(sz[e.to]>sz[g[cur][0].to]) swap(e,g[cur][0]);}}void dfs_hld(int cur,int p){in[cur] = pos++;for(auto& e:g[cur]) if(e.to!=p){head[e.to] = (e.to==g[cur][0].to? head[cur]:e.to);dfs_hld(e.to,cur);}out[cur] = pos;}public:HeavLightDecomposition(){}HeavLightDecomposition(int N,int root,vvec<edge> tree):g(tree),sz(N),in(N),out(N),head(N),par(N){pos = 0;dfs_sz(root,-1);dfs_hld(root,-1);}int lca(int u,int v){while(true){if(in[u]>in[v]) swap(u,v);if(head[u]==head[v]) return u;v = par[head[v]];}}template<class T,class G>void update(int u,int v,const T& x,const G& g, bool isedge=false){while(true){if(in[u]>in[v]) swap(u,v);if(head[u]==head[v]) break;g(in[head[v]],in[v]+1,x);v = par[head[v]];}g(in[u]+isedge,in[v]+1,x);}template<class T,class F,class Q>T query(int u,int v,const T &e,const F& f,const Q& q,bool isedge=false){T l = e,r = e;while(true){if(in[u]>in[v]){swap(u,v); swap(l,r);}if(head[u]==head[v]) break;l = f(q(in[head[v]],in[v]+1),l);v = par[head[v]];}//非可換演算のときは左を反転!//f(rev(f(q(a,b),l),r);return f(f(q(in[u]+isedge,in[v]+1),l),r);}};constexpr ll inf = 1e18;auto op = [](ll a,ll b){return min(a,b);};int main(){cin.tie(0);ios::sync_with_stdio(false);int N,Q,C;cin >> N >> Q >> C;vvec<edge> g(N);rep(i,N-1){int a,b,c;cin >> a >> b >> c;a--,b--;g[a].push_back({b,c});g[b].push_back({a,c});}vec<int> X(Q);rep(i,Q){cin >> X[i];X[i]--;}HeavLightDecomposition HLD(N,0,g);vec<ll> D(N);auto dfs = [&](auto&& self,int cur,int par)->void{for(auto& [to,d]:g[cur]) if(to!=par){D[to] = D[cur]+d;self(self,to,cur);}};dfs(dfs,0,-1);auto dist = [&](int a,int b){return D[a]+D[b]-2*D[HLD.lca(a,b)];};DualSegmentTree seg(N,op,inf);vec<decltype(seg)> dp;rep(i,Q) dp.push_back(seg);dp[0].update(HLD.in[X[0]],HLD.in[X[0]]+1,0);rep(i,Q-1){auto update = [&](int l,int r,ll x){dp[i+1].update(l,r,x);};ll best = inf;rep(j,N){int n = HLD.in[j];if(dp[i][n]==inf) continue;ll val = dp[i][n]+dist(X[i],X[i+1]);HLD.update(j,j,val,update);chmin(best,val);ll c = dp[i][n]+dist(j,X[i+1])+C;HLD.update(j,X[i+1],c,update);}HLD.update(X[i],X[i+1],best,update);}ll ans = inf;rep(i,N) chmin(ans,dp[Q-1][i]);cout << ans << "\n";}