結果
問題 | No.1212 Second Path |
ユーザー | snow39 |
提出日時 | 2020-09-05 17:20:11 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 792 ms / 3,000 ms |
コード長 | 6,505 bytes |
コンパイル時間 | 1,958 ms |
コンパイル使用メモリ | 125,048 KB |
実行使用メモリ | 80,896 KB |
最終ジャッジ日時 | 2024-11-29 01:29:43 |
合計ジャッジ時間 | 25,839 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 326 ms
79,104 KB |
testcase_01 | AC | 792 ms
77,696 KB |
testcase_02 | AC | 734 ms
73,600 KB |
testcase_03 | AC | 765 ms
74,496 KB |
testcase_04 | AC | 733 ms
65,280 KB |
testcase_05 | AC | 755 ms
65,536 KB |
testcase_06 | AC | 372 ms
47,900 KB |
testcase_07 | AC | 483 ms
48,000 KB |
testcase_08 | AC | 467 ms
48,256 KB |
testcase_09 | AC | 471 ms
48,128 KB |
testcase_10 | AC | 473 ms
48,256 KB |
testcase_11 | AC | 474 ms
48,128 KB |
testcase_12 | AC | 521 ms
48,256 KB |
testcase_13 | AC | 475 ms
48,000 KB |
testcase_14 | AC | 514 ms
48,128 KB |
testcase_15 | AC | 510 ms
48,128 KB |
testcase_16 | AC | 484 ms
48,000 KB |
testcase_17 | AC | 360 ms
78,924 KB |
testcase_18 | AC | 74 ms
6,528 KB |
testcase_19 | AC | 79 ms
6,656 KB |
testcase_20 | AC | 76 ms
6,656 KB |
testcase_21 | AC | 71 ms
6,784 KB |
testcase_22 | AC | 73 ms
6,784 KB |
testcase_23 | AC | 63 ms
6,232 KB |
testcase_24 | AC | 61 ms
6,300 KB |
testcase_25 | AC | 59 ms
6,400 KB |
testcase_26 | AC | 60 ms
6,272 KB |
testcase_27 | AC | 60 ms
6,428 KB |
testcase_28 | AC | 61 ms
6,384 KB |
testcase_29 | AC | 611 ms
80,896 KB |
testcase_30 | AC | 598 ms
80,896 KB |
testcase_31 | AC | 583 ms
80,812 KB |
testcase_32 | AC | 412 ms
37,888 KB |
testcase_33 | AC | 320 ms
30,336 KB |
testcase_34 | AC | 475 ms
45,568 KB |
testcase_35 | AC | 149 ms
10,752 KB |
testcase_36 | AC | 387 ms
39,296 KB |
testcase_37 | AC | 356 ms
36,480 KB |
testcase_38 | AC | 380 ms
37,888 KB |
testcase_39 | AC | 280 ms
24,192 KB |
testcase_40 | AC | 98 ms
7,296 KB |
testcase_41 | AC | 397 ms
38,144 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 2 ms
5,248 KB |
testcase_44 | AC | 2 ms
5,248 KB |
testcase_45 | AC | 349 ms
48,028 KB |
testcase_46 | AC | 373 ms
48,024 KB |
testcase_47 | AC | 374 ms
48,020 KB |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} #include <functional> #include <climits> //SegmentTree<int> seg(N,[](int a,int b){return min(a,b);},INT_MAX); template< typename T> class SegmentTree{ public: using F = function<T(T,T)>; int n; vector<T> tree; F operation; T def; SegmentTree(int size,F _operation,T _def):operation(_operation),def(_def){ n=1; while(n<size) n*=2; tree.resize(2*n-1,def); } SegmentTree(){} void embody(int size,F _operation,T _def){ operation=_operation; def=_def; n=1; while(n<size) n*=2; tree.resize(2*n-1,def); } void initialize(vector<T> v){ int vSize=v.size(); n=1; while(n<vSize) n*=2; tree.resize(2*n-1,def); for(int i=0;i<vSize;i++) tree[i+n-1]=v[i]; for(int i=n-2;i>=0;i--) tree[i]=operation(tree[2*i+1],tree[2*i+2]); } void update(int index,T value){ index+=n-1; tree[index]=value; while(index>0){ index=(index-1)/2; tree[index]=operation(tree[2*index+1],tree[2*index+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1){//[a,b),getMin(a,b,0,0,-1) if(r<0) r=n; if(r<=a||b<=l) return def; else if(a<=l&&r<=b) return tree[k]; else{ T lval=query(a,b,2*k+1,l,(l+r)/2); T rval=query(a,b,2*k+2,(l+r)/2,r); return operation(lval,rval); } } int find(int x,int k=0,int l=0,int r=-1){// a[0]+...+a[i]>=x (i:minimal) if(r<0) r=n; if(r-l==1) return k-(n-1); if(tree[2*k+1]>=x) return find(x,2*k+1,l,(l+r)/2); else return find(x-tree[2*k+1],2*k+2,(l+r)/2,r); } int find_left(int a,int b,T x,int k=0,int l=0,int r=-1){// max(a[a],...,a[i])>=x (i:minimal) if(r<0) r=n; if(tree[k]<x||r<=a||b<=l) return -1; if(r-l==1) return k-(n-1); int vl=find_left(a,b,x,2*k+1,l,(l+r)/2); if(vl>=0) return vl; return find_left(a,b,x,2*k+2,(l+r)/2,r); } }; struct LowestCommonAncestor{ #define MAX_LOG_V 25 vector<vector<int>> g; int root; vector<int> parent[MAX_LOG_V]; vector<int> depth; LowestCommonAncestor(){} LowestCommonAncestor(int V,int root_):g(V),depth(V){ root=root_; for(int i=0;i<MAX_LOG_V;i++) parent[i].resize(V); } void initialize(int V,int root_){ g.resize(V); depth.resize(V,0); root=root_; for(int i=0;i<MAX_LOG_V;i++) parent[i].resize(V); } void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); } void dfs(int v,int p,int d){ parent[0][v]=p; depth[v]=d; for(int i=0;i<g[v].size();i++){ if(g[v][i]!=p) dfs(g[v][i],v,d+1); } } void build(int V){ dfs(root,-1,0); for(int k=0;k+1<MAX_LOG_V;k++){ for(int v=0;v<V;v++){ if(parent[k][v]<0) parent[k+1][v]=-1; else parent[k+1][v]=parent[k][parent[k][v]]; } } } int query(int u,int v){ if(depth[u]>depth[v]) swap(u,v); for(int k=0;k<MAX_LOG_V;k++){ if((depth[v]-depth[u])>>k&1){ v=parent[k][v]; } } if(u==v) return u; for(int k=MAX_LOG_V-1;k>=0;k--){ if(parent[k][u]!=parent[k][v]){ u=parent[k][u]; v=parent[k][v]; } } return parent[0][u]; } }; int N; vector<vector<pair<int,ll>>> g; int Q; vector<int> X,Y; vector<int> L; LowestCommonAncestor lca; vector<ll> dist; vector<vector<pair<ll,int>>> miedge; const ll INF=1e15; SegmentTree<ll> seg; vector<vector<int>> qxy,qlca; vector<int> trans; int segpos=0; vector<ll> ans; void predfs(int now,int par,ll d){ dist[now]=d; for(auto e:g[now]){ int nex=e.first; ll c=e.second; for(int i=0;i<3;i++){ if(miedge[now][i].first>c){ for(int j=2;j-1>=i;j--) miedge[now][j]=miedge[now][j-1]; miedge[now][i]=mkp(c,nex); break; } } if(nex==par) continue; predfs(nex,now,d+c); } } void eulertour(int now,int par){ for(auto tar:qxy[now]){// x (x != lca(x,y)) if(miedge[now][0].second==par) chmin(ans[tar],miedge[now][1].first); else chmin(ans[tar],miedge[now][0].first); if(par==L[tar]) continue; int lef=trans[L[tar]]; ll res=seg.query(lef+1,segpos); chmin(ans[tar],res); } for(auto tar:qlca[now]){// lca for(int i=0;i<3;i++){ int chnode=miedge[now][i].second; int lc=lca.query(X[tar],chnode); if(lc!=par&&lc!=L[tar]) continue; lc=lca.query(Y[tar],chnode); if(lc!=par&&lc!=L[tar]) continue; chmin(ans[tar],miedge[now][i].first); } } for(auto e:g[now]){ int nex=e.first; ll c=e.second; if(nex==par) continue; ll nc=INF; for(int i=0;i<3;i++){ if(miedge[now][i].second==par) continue; if(miedge[now][i].second==nex) continue; nc=miedge[now][i].first; break; } seg.update(segpos,nc); trans[now]=segpos++; eulertour(nex,now); segpos--; trans[now]=-1; seg.update(segpos,INF); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N; g.resize(N); lca.initialize(N,0); dist.resize(N,0); rep(i,N-1){ int a,b,c; cin>>a>>b>>c; a--;b--; g[a].push_back(mkp(b,c)); g[b].push_back(mkp(a,c)); lca.add_edge(a,b); } lca.build(N); cin>>Q; X.resize(Q); Y.resize(Q); L.resize(Q); rep(i,Q) cin>>X[i]>>Y[i]; rep(i,Q){ X[i]--;Y[i]--; L[i]=lca.query(X[i],Y[i]); } miedge.resize(N); rep(i,N){ miedge[i].resize(3); rep(j,3) miedge[i][j]=mkp(INF,-1); } seg.embody(N,[](ll a,ll b){return min(a,b);},INF); qxy.resize(N); qlca.resize(N); rep(i,Q){ if(X[i]!=L[i]) qxy[X[i]].push_back(i); if(Y[i]!=L[i]) qxy[Y[i]].push_back(i); qlca[L[i]].push_back(i); } trans.resize(N,-1); ans.resize(Q,INF); predfs(0,-1,0); eulertour(0,-1); rep(i,Q){ if(ans[i]==INF) ans[i]=-1; else ans[i]=2*ans[i]+dist[X[i]]+dist[Y[i]]-2*dist[L[i]]; } rep(i,Q) cout<<ans[i]<<"\n"; return 0; }