結果
問題 | No.1212 Second Path |
ユーザー | penguinman |
提出日時 | 2020-08-08 18:06:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 436 ms / 3,000 ms |
コード長 | 5,314 bytes |
コンパイル時間 | 2,747 ms |
コンパイル使用メモリ | 197,896 KB |
実行使用メモリ | 65,440 KB |
最終ジャッジ日時 | 2024-04-23 03:47:58 |
合計ジャッジ時間 | 18,924 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 226 ms
64,924 KB |
testcase_01 | AC | 397 ms
63,000 KB |
testcase_02 | AC | 436 ms
59,548 KB |
testcase_03 | AC | 421 ms
60,188 KB |
testcase_04 | AC | 421 ms
52,508 KB |
testcase_05 | AC | 415 ms
52,892 KB |
testcase_06 | AC | 258 ms
41,424 KB |
testcase_07 | AC | 311 ms
38,976 KB |
testcase_08 | AC | 308 ms
39,116 KB |
testcase_09 | AC | 303 ms
39,108 KB |
testcase_10 | AC | 320 ms
39,368 KB |
testcase_11 | AC | 325 ms
38,984 KB |
testcase_12 | AC | 313 ms
39,104 KB |
testcase_13 | AC | 310 ms
38,984 KB |
testcase_14 | AC | 308 ms
39,116 KB |
testcase_15 | AC | 322 ms
39,424 KB |
testcase_16 | AC | 325 ms
38,948 KB |
testcase_17 | AC | 230 ms
63,904 KB |
testcase_18 | AC | 49 ms
8,724 KB |
testcase_19 | AC | 50 ms
9,260 KB |
testcase_20 | AC | 51 ms
8,948 KB |
testcase_21 | AC | 48 ms
9,672 KB |
testcase_22 | AC | 52 ms
9,468 KB |
testcase_23 | AC | 31 ms
7,436 KB |
testcase_24 | AC | 39 ms
7,520 KB |
testcase_25 | AC | 36 ms
7,332 KB |
testcase_26 | AC | 37 ms
7,524 KB |
testcase_27 | AC | 38 ms
7,700 KB |
testcase_28 | AC | 40 ms
8,024 KB |
testcase_29 | AC | 339 ms
65,440 KB |
testcase_30 | AC | 347 ms
65,432 KB |
testcase_31 | AC | 328 ms
65,436 KB |
testcase_32 | AC | 243 ms
32,016 KB |
testcase_33 | AC | 195 ms
26,472 KB |
testcase_34 | AC | 292 ms
37,348 KB |
testcase_35 | AC | 97 ms
12,468 KB |
testcase_36 | AC | 256 ms
32,876 KB |
testcase_37 | AC | 234 ms
31,032 KB |
testcase_38 | AC | 232 ms
32,056 KB |
testcase_39 | AC | 159 ms
22,092 KB |
testcase_40 | AC | 62 ms
10,068 KB |
testcase_41 | AC | 243 ms
32,432 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,940 KB |
testcase_44 | AC | 2 ms
6,940 KB |
testcase_45 | AC | 254 ms
41,296 KB |
testcase_46 | AC | 249 ms
41,424 KB |
testcase_47 | AC | 256 ms
41,296 KB |
ソースコード
#include<bits/stdc++.h> #define endl "\n" using std::cin; using std::cout; using std::vector; using ll=long long; const ll inf=(1ll<<60); struct tree{ int N; vector<vector<int>> dp; vector<int> dist; tree(vector<vector<int>> edge){ N=edge.size(); dp.resize(N); dist.resize(N,-1); for(int i=0;i<N;i++) dp[i].resize(20); dist[0]=dp[0][0]=0; std::queue<int> que; que.push(0); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0;i<edge[now].size();i++){ int next=edge[now][i]; if(dist[next]==-1){ dist[next]=dist[now]+1; que.push(next); dp[next][0]=now; } } } for(int i=1;i<20;i++){ for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1]; } } std::tuple<int,int,int> LCA(int X,int Y){ if(dist[X]<dist[Y]) std::swap(X,Y); int x=X; { int Z=dist[X]-dist[Y]; for(int i=0;i<20;i++){ if(Z&(1<<i)){ X=dp[X][i]; } } Z=dist[x]-dist[Y]-1; for(int i=0;i<20;i++){ if(Z&(1<<i)){ x=dp[x][i]; } } } if(X==Y){ return std::make_tuple(X,x,-1); } for(int i=19;i>=0;i--){ if(dp[X][i]!=dp[Y][i]){ X=dp[X][i]; Y=dp[Y][i]; } } return std::make_tuple(dp[X][0],X,Y); } }; struct Segment_tree{ int N; vector<ll> node; Segment_tree(int n):N(n){ { int X=1; while(X<N) X*=2; N=X; } node.resize(2*N-1,inf); } ll compare(ll X,ll Y){ return std::min(X,Y); } void update(int X,ll Y){ X+=N-1; node[X]=Y; while(X){ X=(X-1)/2; node[X]=compare(node[X*2+1],node[X*2+2]); } } ll query(int a,int b,int now,int l,int r){ if(r<0) r=N; if(r<=a||b<=l) return inf; if(a<=l&&r<=b) return node[now]; return compare(query(a,b,now*2+1,l,(r+l)/2),query(a,b,now*2+2,(r+l)/2,r)); } }; int match[100000]; void dfs(int N,int now,vector<vector<int>> &edge,vector<vector<int>> &weight,tree &tr,Segment_tree &seg,vector<vector<std::tuple<int,int,int>>> &memo,vector<ll> &min){ vector<ll> data; ll m=inf; for(int i=0;i<edge[now].size();i++){ int next=edge[now][i]; if(tr.dist[next]>tr.dist[now]) data.push_back(weight[now][i]); else m=weight[now][i]; } sort(data.begin(),data.end()); for(int i=0;i<edge[now].size();i++){ int next=edge[now][i]; if(tr.dist[next]>tr.dist[now]){ ll Z=data[0]; if(Z==weight[now][i]){ if(data.size()==1) Z=inf; else Z=data[1]; } seg.update(tr.dist[now],Z); dfs(N,next,edge,weight,tr,seg,memo,min); match[next]=weight[now][i]; } } for(auto p:memo[now]){ int X,Y,Z; std::tie(X,Y,Z)=p; if(X>=0){ if(data.empty()) data.push_back(inf); min[X]=std::min({min[X],seg.query(Y+1,Z,0,0,-1),data[0]}); } else{ X=-X-1; min[X]=std::min(min[X],m); vector<int> child; if(Y>=0) child.push_back(match[Y]); if(Z>=0) child.push_back(match[Z]); sort(child.begin(),child.end()); int now=0; for(int i=0;i<data.size();i++){ if(now==child.size()||child[now]!=data[i]){ min[X]=std::min(min[X],data[i]); break; } else now++; } } } } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N; cin>>N; vector<vector<int>> edge(N),weight(N); for(int i=1;i<N;i++){ int X,Y,Z; cin>>X>>Y>>Z; edge[X-1].push_back(Y-1); edge[Y-1].push_back(X-1); weight[X-1].push_back(Z); weight[Y-1].push_back(Z); } tree tr(edge); int Q; cin>>Q; vector<vector<std::tuple<int,int,int>>> memo(N); vector<ll> min(Q,inf),sum(Q),dist(N,-1); dist[0]=0; std::queue<int> que; que.push(0); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0;i<edge[now].size();i++){ int next=edge[now][i]; if(dist[next]==-1){ dist[next]=dist[now]+weight[now][i]; que.push(next); } } } for(int i=0;i<Q;i++){ int X,Y; cin>>X>>Y; X--,Y--; int Z,x,y; std::tie(Z,x,y)=tr.LCA(X,Y); if(X!=Z) memo[X].push_back(std::make_tuple(i,tr.dist[Z],tr.dist[X])); if(Y!=Z) memo[Y].push_back(std::make_tuple(i,tr.dist[Z],tr.dist[Y])); memo[Z].push_back(std::make_tuple(-i-1,x,y)); sum[i]=dist[X]+dist[Y]-2*dist[Z]; } Segment_tree seg(N); dfs(N,0,edge,weight,tr,seg,memo,min); for(int i=0;i<Q;i++){ sum[i]+=min[i]*2; if(min[i]==inf) sum[i]=-1; cout<<sum[i]<<endl; } }