結果

問題 No.1212 Second Path
ユーザー penguinmanpenguinman
提出日時 2020-08-01 19:09:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,935 bytes
コンパイル時間 3,170 ms
コンパイル使用メモリ 209,252 KB
実行使用メモリ 74,004 KB
最終ジャッジ日時 2024-04-23 03:55:59
合計ジャッジ時間 12,823 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
    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;
    }
}
0