結果
問題 | No.1212 Second Path |
ユーザー |
![]() |
提出日時 | 2020-07-31 00:41:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 956 ms / 3,000 ms |
コード長 | 5,425 bytes |
コンパイル時間 | 2,741 ms |
コンパイル使用メモリ | 208,544 KB |
実行使用メモリ | 110,420 KB |
最終ジャッジ日時 | 2024-10-15 03:25:46 |
合計ジャッジ時間 | 25,299 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#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(30);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<30;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<30;i++){if(Z&(1<<i)){X=dp[X][i];}}Z=dist[x]-dist[Y]-1;for(int i=0;i<30;i++){if(Z&(1<<i)){x=dp[x][i];}}}if(X==Y){return std::make_tuple(X,x,-1);}for(int i=29;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));}};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;std::map<int,int> cnt,match;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]);cnt[weight[now][i]]++;match[next]=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);seg.update(tr.dist[now],inf);}}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;cnt[match[Y]]--;if(cnt[match[Y]]==0) cnt.erase(match[Y]);if(Z>=0){cnt[match[Z]]--;if(cnt[match[Z]]==0) cnt.erase(match[Z]);}if(!cnt.empty()) min[X]=std::min(min[X],(ll)(*begin(cnt)).first);cnt[match[Y]]++;if(Z>=0) cnt[match[Z]]++;}}}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);const ll MAX=1e5;const ll INF=1e9;int N; cin>>N;assert(1<=N&&N<=MAX);vector<vector<int>> edge(N),weight(N);for(int i=1;i<N;i++){int X,Y,Z; cin>>X>>Y>>Z;assert(1<=X&&X<=N&&1<=Y&&Y<=N&&1<=Z&&Z<=INF);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;assert(1<=Q&&Q<=MAX);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;assert(1<=X&&X<=N&&1<=Y&&Y<=N&&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;}}