結果
| 問題 | No.1212 Second Path |
| ユーザー |
 penguinman
|
| 提出日時 | 2020-08-01 19:11:32 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,956 bytes |
| コンパイル時間 | 2,803 ms |
| コンパイル使用メモリ | 212,564 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-15 03:27:06 |
| 合計ジャッジ時間 | 9,873 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 RE * 33 |
ソースコード
#include<bits/stdc++.h>//using namespace std;#pragma GCC target("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++)#define REP(i,j,n) for(ll i=(ll)(j);i<=(ll)(n);i++)#define per(i,j,n) for(ll i=(ll)(j);(ll)(n)<=i;i--)#define ll long long#define ALL(a) (a).begin(),(a).end()#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key)))#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key)))#define pb emplace_back#define mp std::make_pair//#define endl "\n"//using std::endl;using std::cin;using std::cout;using std::vector;using std::string;using std::upper_bound;using std::lower_bound;using vi=vector<ll>;using vii=vector<vi>;using pii=std::pair<ll,ll>;//constexpr ll MOD=1e9+7;//constexpr ll MOD=998244353;//constexpr ll MOD=10000000;//constexpr ll MOD=1e4;constexpr ll MAX=3e6;constexpr ll inf=(1ll<<60);template<class T>class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};template<typename T>struct Segment_tree{ll N;T mem;vector<T> node;Segment_tree(vector<T> &X,T m):mem(m){ll sz=X.size();N=1;while(N<sz) N*=2;node.resize(2*N-1,mem);rep(i,0,sz) node[N-1+i]=X[i];per(i,N-2,0){node[i]=Compare(node[i*2+1],node[i*2+2]);}}T Compare(T &A,T &B){return std::max(A,B);}void update(ll X,T val){X+=N-1;node[X]=val;while(X>0){X=(X-1)/2;node[X]=Compare(node[X*2+1],node[X*2+2]);}}T Query(ll a,ll b,ll now,ll l,ll r){ //[a,b),[l,r)if(r<0) r=N;if(r<=a||b<=l) return mem;if(a<=l&&r<=b) return node[now];auto vl=Query(a,b,now*2+1,l,(l+r)/2),vr=Query(a,b,now*2+2,(l+r)/2,r);return Compare(vl,vr);}};struct Tree{int N;vector<vector<int>> dp;vector<int> dist,par;vi dist2;Tree(vii edge){N=edge.size();dp.resize(N);dist.resize(N,-1);dist2.resize(N,-1);par.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]=par[next]=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];}}int LCA(int X,int Y){if(dist[X]<dist[Y]) std::swap(X,Y);{int Z=dist[X]-dist[Y];for(int i=0;i<30;i++){if(Z&(1<<i)){X=dp[X][i];}}}if(X==Y) return X;for(int i=29;i>=0;i--){if(dp[X][i]!=dp[Y][i]){X=dp[X][i];Y=dp[Y][i];}}return dp[X][0];}void make_dist2(vii edge,vii weight){std::queue<int> que;que.push(0);dist2[0]=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(dist2[next]==-1){dist2[next]=dist2[now]+weight[now][i];que.push(next);}}}}};struct Binary_indexed_tree{int N;vi bit;Binary_indexed_tree(int n):N(n){bit.resize(N+1,0);}void add(int x,ll a){for(x;x<=N;x+=(x&-x)) bit[x]+=a;}ll sum(int x){ll ret=0;for(x;x>0;x-=(x&-x)) ret+=bit[x];return ret;}ll lower_bound(ll X){if(sum(N)<X) return -1;ll ret=0,memo=1,sum=0;while(memo*2<=N) memo*=2;while(memo>0){if(memo+ret<=N&&sum+bit[memo+ret]<X){sum+=bit[memo+ret];ret+=memo;}memo/=2;}return ret+1;}};struct Union_Find{ll N;vi par;vi siz;Union_Find(int n):N(n){par.resize(N);siz.resize(N,1);rep(i,0,N) par[i]=i;}ll root(ll X){if(par[X]==X) return X;return par[X]=root(par[X]);}bool same(ll X,ll Y){return root(X)==root(Y);}void unite(ll X,ll Y){X=root(X);Y=root(Y);if(X==Y) return;par[X]=Y;siz[Y]+=siz[X];siz[X]=0;}ll size(ll X){return siz[root(X)];}};long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}vi fac,finv,inv;void COMinit() {fac.resize(MAX);finv.resize(MAX);inv.resize(MAX);fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}ll COM(ll n,ll r){if(n<r||n<0||r<0) return 0;return fac[n]*finv[r]%MOD*finv[n-r]%MOD;}void comp(vi &A){std::map<ll,ll> memo;rep(i,0,A.size()) memo[A[i]]=0;ll cnt=1;for(auto &p:memo) p.second=cnt++;rep(i,0,A.size()) A[i]=memo[A[i]];}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);ll N; cin>>N;assert(N<=5000);vii edge(N),weight(N);rep(i,1,N){ll X,Y,Z; cin>>X>>Y>>Z;edge[X-1].pb(Y-1);edge[Y-1].pb(X-1);weight[X-1].pb(Z);weight[Y-1].pb(Z);}Tree tr(edge);ll Q; cin>>Q;vii memo(N);vi pardist(N,inf);std::map<pii,ll> to;rep(i,0,N){rep(j,0,edge[i].size()){int X=edge[i][j];if(X==tr.par[i]) pardist[i]=weight[i][j];else memo[i].pb(weight[i][j]);to[mp(i,X)]=weight[i][j];}sort(ALL(memo[i]));}tr.make_dist2(edge,weight);rep(i,0,Q){ll X,Y; cin>>X>>Y;X--,Y--;ll Z=tr.LCA(X,Y);ll ans=tr.dist2[Y]+tr.dist2[X]-tr.dist2[Z]*2;ll min=inf,me=-1;while(X!=Z){ll P=inf;if(memo[X].size()>0){if(memo[X][0]==me){if(memo[X].size()>1) P=memo[X][1];}else P=memo[X][0];}min=std::min(min,P);if(tr.par[X]==Z) break;me=pardist[X];X=tr.par[X];}std::swap(X,Y);while(X!=Z){ll P=inf;if(memo[X].size()>0){if(memo[X][0]==me){if(memo[X].size()>1) P=memo[X][1];}else P=memo[X][0];}min=std::min(min,P);if(tr.par[X]==Z) break;me=pardist[X];X=tr.par[X];}std::map<ll,ll> map;rep(i,0,std::min(3,(int)memo[Z].size())) map[memo[Z][i]]++;map[pardist[Z]]++;if(to.count(mp(X,Z))&&map.count(to[mp(X,Z)])){map[to[mp(X,Z)]]--;if(map[to[mp(X,Z)]]==0) map.erase(to[mp(X,Z)]);}std::swap(X,Y);if(to.count(mp(X,Z))&&map.count(to[mp(X,Z)])){map[to[mp(X,Z)]]--;if(map[to[mp(X,Z)]]==0) map.erase(to[mp(X,Z)]);}if(!map.empty()) min=std::min(min,(*begin(map)).first);if(min==inf) ans=-1;else ans+=min*2;cout<<ans<<endl;}}