結果

問題 No.1212 Second Path
ユーザー ChanyuhChanyuh
提出日時 2020-08-31 21:13:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,406 ms / 3,000 ms
コード長 6,427 bytes
コンパイル時間 1,893 ms
コンパイル使用メモリ 136,264 KB
実行使用メモリ 40,448 KB
最終ジャッジ日時 2024-11-17 02:25:19
合計ジャッジ時間 29,376 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 451 ms
40,448 KB
testcase_01 AC 1,406 ms
40,192 KB
testcase_02 AC 1,392 ms
39,552 KB
testcase_03 AC 1,368 ms
39,552 KB
testcase_04 AC 1,362 ms
38,272 KB
testcase_05 AC 1,376 ms
38,272 KB
testcase_06 AC 336 ms
33,940 KB
testcase_07 AC 519 ms
34,560 KB
testcase_08 AC 514 ms
34,688 KB
testcase_09 AC 498 ms
34,560 KB
testcase_10 AC 493 ms
34,560 KB
testcase_11 AC 505 ms
34,560 KB
testcase_12 AC 498 ms
34,688 KB
testcase_13 AC 482 ms
34,560 KB
testcase_14 AC 488 ms
34,688 KB
testcase_15 AC 495 ms
34,560 KB
testcase_16 AC 529 ms
34,560 KB
testcase_17 AC 469 ms
40,448 KB
testcase_18 AC 180 ms
5,888 KB
testcase_19 AC 182 ms
5,888 KB
testcase_20 AC 173 ms
5,760 KB
testcase_21 AC 186 ms
5,760 KB
testcase_22 AC 187 ms
5,888 KB
testcase_23 AC 158 ms
5,888 KB
testcase_24 AC 166 ms
5,760 KB
testcase_25 AC 164 ms
5,760 KB
testcase_26 AC 164 ms
5,888 KB
testcase_27 AC 165 ms
5,760 KB
testcase_28 AC 174 ms
5,760 KB
testcase_29 AC 857 ms
40,448 KB
testcase_30 AC 972 ms
40,448 KB
testcase_31 AC 944 ms
40,448 KB
testcase_32 AC 417 ms
27,264 KB
testcase_33 AC 400 ms
22,272 KB
testcase_34 AC 502 ms
32,640 KB
testcase_35 AC 239 ms
8,320 KB
testcase_36 AC 437 ms
28,032 KB
testcase_37 AC 417 ms
25,984 KB
testcase_38 AC 434 ms
27,008 KB
testcase_39 AC 352 ms
17,664 KB
testcase_40 AC 209 ms
6,016 KB
testcase_41 AC 443 ms
27,136 KB
testcase_42 AC 4 ms
5,760 KB
testcase_43 AC 4 ms
5,760 KB
testcase_44 AC 3 ms
5,888 KB
testcase_45 AC 336 ms
33,940 KB
testcase_46 AC 348 ms
33,864 KB
testcase_47 AC 350 ms
33,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, ll> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int n;
vector<P> G[100010];
int depth[100010],par[100010][17];
ll len[100010],table[100010][17];


void dfs(int s,int p,ll w){
    //cout << s << endl;
    if(p!=-1){
        len[s]=len[p]+w;
        depth[s]=depth[p]+1;
    }
    par[s][0]=p;
    rep(k,16){
        if(par[s][k]!=-1) par[s][k+1]=par[par[s][k]][k];
        else par[s][k+1]=-1;
        //cout << s << " " << par[s][k+1] << endl;
    }
    for(P pa:G[s]){
        int t=pa.first;ll w_=pa.second;
        //cout << t << " " << s << " " << w_ << endl;
        if(t==p || t==-1) continue;
        dfs(t,s,w_);
    }
}

int lca(int x,int y){
    //cout << x << " " << y << endl;
    //cout << depth[x] << " " << depth[y] << endl;
    if(depth[x]<depth[y]) swap(x,y);
    int l=depth[x]-depth[y];
    //cout << l << endl;
    rep(i,17){
        if(l&(1 << i)){
            x=par[x][i];
            l^=(1 << i);
        }
    }
    //cout << x << " " << y << endl;
    if(x==y) return x;
    per(i,17){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    return par[x][0];
}

bool in_pass(int s,int t,int x){
    //cout << s << " " << t << " " << x << endl; 
    if(x==-1) return false;
    if(depth[s]>depth[t]) swap(s,t);
    if(depth[s]>depth[x]) return false;
    if(lca(t,x)==x) return true;
    return false;
}

void make_table(){
    rep(i,n) table[i][0]=INF;
    rep(j,16){
        rep(i,n){
            ll res=INF;
            if(par[i][j+1]==-1){
                table[i][j+1]=INF;
                continue;
            }
            for(P p:G[par[i][j]]){
                int t=p.first;ll l=p.second;
                if(in_pass(par[i][j+1],i,t)) continue;
                //int q=lca(i,t);
                //cout << par[i][j+1] << " " << i << " " << t << " " << q << " " <<  in_pass(par[i][j+1],i,t) << endl;
                res=l;
                break;
            }
            table[i][j+1]=min(res,min(table[i][j],table[par[i][j]][j]));
        }
    }
}

void solve(){
    cin >> n;
    rep(i,n-1){
        int a,b,c;cin >> a >> b >> c;a--;b--;
        G[a].push_back(P(b,c));
        G[b].push_back(P(a,c));
    }
    rep(i,n) G[i].push_back(P(-1,INF));
    rep(i,n) sort(G[i].begin(),G[i].end(),[](P a,P b){return a.second<b.second;});
    dfs(0,-1,0);
    make_table();
    // rep(i,n){
    //     per(j,17){
    //         cout << i << " " << j << " " << table[i][j] << endl;
    //     }
    // }
    int q;cin >> q;
    rep(_,q){
        int u,v;cin >> u >> v;u--;v--;
        int l=lca(u,v);
        ll D=len[u]+len[v]-2ll*len[l];
        //cout << u << " " << v << endl;
        if(u!=l && v!=l){
            ll res=INF;
            int u_=u,v_=v;
            per(i,17){
                if((depth[u_]-depth[l])&(1 << i)){
                    res=min(res,table[u_][i]);
                    u_=par[u_][i];
                    if(u_==l) break;
                    for(P p:G[u_]){
                        int t=p.first;ll d=p.second;
                        if(in_pass(u,l,t)) continue;
                        res=min(res,d);
                        break;
                    }
                }
            }
            per(i,17){
                if((depth[v_]-depth[l])&(1 << i)){
                    res=min(res,table[v_][i]);
                    v_=par[v_][i];
                    if(v_==l) break;
                    for(P p:G[v_]){
                        int t=p.first;ll d=p.second;
                        if(in_pass(v,l,t)) continue;
                        res=min(res,d);
                        break;
                    }
                }
            }
            for(P p:G[u]){
                int t=p.first;ll d=p.second;
                if(in_pass(u,l,t)) continue;
                res=min(res,d);
                break;
            }
            for(P p:G[v]){
                int t=p.first;ll d=p.second;
                if(in_pass(v,l,t)) continue;
                res=min(res,d);
                break;
            }
            for(P p:G[l]){
                int t=p.first;ll d=p.second;
                if(in_pass(u,l,t) || in_pass(v,l,t)) continue;
                res=min(res,d);
                break;
            }
            if(res==INF) cout << -1 << endl;
            else cout << 2ll*res+D << endl;
            continue;
        }
        if(v==l) swap(u,v);
        int v_=v;
        ll res=INF;
        per(i,17){
            if((depth[v_]-depth[l])&(1 << i)) {
                res=min(res,table[v_][i]);
                v_=par[v_][i];
                for(P p:G[v_]){
                    int t=p.first;ll d=p.second;
                    if(in_pass(v,l,t)) continue;
                    res=min(res,d);
                    break;
                }
            }
        }
        //cout << res << endl;
        for(P p:G[u]){
            int t=p.first;ll d=p.second;
            //cout << v << " " << l << " " << t << " " << d << endl;
            if(in_pass(u,v,t)) continue;
            res=min(res,d);
            break;
        }
        for(P p:G[v]){
            int t=p.first;ll d=p.second;
            //cout << v << " " << l << " " << t << " " << d << endl;
            if(in_pass(u,v,t)) continue;
            res=min(res,d);
            break;
        }
        if(res==INF) cout << -1 << endl;
        else cout << 2ll*res+D << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}
0