結果

問題 No.1212 Second Path
ユーザー penguinmanpenguinman
提出日時 2020-08-01 13:04:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 929 ms / 3,000 ms
コード長 5,425 bytes
コンパイル時間 2,707 ms
コンパイル使用メモリ 210,420 KB
実行使用メモリ 110,424 KB
最終ジャッジ日時 2024-10-15 03:26:15
合計ジャッジ時間 25,314 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 337 ms
105,172 KB
testcase_01 AC 693 ms
103,632 KB
testcase_02 AC 678 ms
94,996 KB
testcase_03 AC 677 ms
96,596 KB
testcase_04 AC 661 ms
77,016 KB
testcase_05 AC 668 ms
77,524 KB
testcase_06 AC 907 ms
52,348 KB
testcase_07 AC 448 ms
41,728 KB
testcase_08 AC 462 ms
41,780 KB
testcase_09 AC 486 ms
41,596 KB
testcase_10 AC 482 ms
41,984 KB
testcase_11 AC 481 ms
41,728 KB
testcase_12 AC 491 ms
41,720 KB
testcase_13 AC 482 ms
41,732 KB
testcase_14 AC 463 ms
41,828 KB
testcase_15 AC 478 ms
41,984 KB
testcase_16 AC 482 ms
41,608 KB
testcase_17 AC 340 ms
104,148 KB
testcase_18 AC 69 ms
8,676 KB
testcase_19 AC 70 ms
9,192 KB
testcase_20 AC 71 ms
8,848 KB
testcase_21 AC 67 ms
9,528 KB
testcase_22 AC 70 ms
9,472 KB
testcase_23 AC 41 ms
7,308 KB
testcase_24 AC 50 ms
7,396 KB
testcase_25 AC 47 ms
7,336 KB
testcase_26 AC 50 ms
7,532 KB
testcase_27 AC 51 ms
7,740 KB
testcase_28 AC 52 ms
7,892 KB
testcase_29 AC 556 ms
110,292 KB
testcase_30 AC 566 ms
110,424 KB
testcase_31 AC 568 ms
110,420 KB
testcase_32 AC 385 ms
33,956 KB
testcase_33 AC 325 ms
28,004 KB
testcase_34 AC 461 ms
40,016 KB
testcase_35 AC 127 ms
12,748 KB
testcase_36 AC 408 ms
35,052 KB
testcase_37 AC 381 ms
32,844 KB
testcase_38 AC 388 ms
33,984 KB
testcase_39 AC 254 ms
23,252 KB
testcase_40 AC 87 ms
10,076 KB
testcase_41 AC 382 ms
34,272 KB
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 2 ms
5,248 KB
testcase_44 AC 2 ms
5,248 KB
testcase_45 AC 929 ms
52,216 KB
testcase_46 AC 917 ms
52,344 KB
testcase_47 AC 912 ms
52,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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