結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 314 ms
102,100 KB
testcase_01 AC 631 ms
100,512 KB
testcase_02 AC 605 ms
91,808 KB
testcase_03 AC 624 ms
93,604 KB
testcase_04 AC 632 ms
74,016 KB
testcase_05 AC 609 ms
74,524 KB
testcase_06 AC 879 ms
49,236 KB
testcase_07 AC 440 ms
38,684 KB
testcase_08 AC 463 ms
38,736 KB
testcase_09 AC 457 ms
38,480 KB
testcase_10 AC 462 ms
38,988 KB
testcase_11 AC 468 ms
38,600 KB
testcase_12 AC 478 ms
38,600 KB
testcase_13 AC 457 ms
38,604 KB
testcase_14 AC 476 ms
38,732 KB
testcase_15 AC 459 ms
38,988 KB
testcase_16 AC 468 ms
38,608 KB
testcase_17 AC 325 ms
101,028 KB
testcase_18 AC 64 ms
8,808 KB
testcase_19 AC 66 ms
9,132 KB
testcase_20 AC 66 ms
9,040 KB
testcase_21 AC 64 ms
9,408 KB
testcase_22 AC 66 ms
9,464 KB
testcase_23 AC 38 ms
7,184 KB
testcase_24 AC 46 ms
7,520 KB
testcase_25 AC 43 ms
7,324 KB
testcase_26 AC 47 ms
7,532 KB
testcase_27 AC 47 ms
7,832 KB
testcase_28 AC 48 ms
8,024 KB
testcase_29 AC 513 ms
107,168 KB
testcase_30 AC 521 ms
107,296 KB
testcase_31 AC 518 ms
107,424 KB
testcase_32 AC 376 ms
31,764 KB
testcase_33 AC 307 ms
26,220 KB
testcase_34 AC 448 ms
37,060 KB
testcase_35 AC 118 ms
12,468 KB
testcase_36 AC 382 ms
32,504 KB
testcase_37 AC 360 ms
30,780 KB
testcase_38 AC 373 ms
31,676 KB
testcase_39 AC 242 ms
21,968 KB
testcase_40 AC 82 ms
10,032 KB
testcase_41 AC 370 ms
32,200 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 871 ms
49,112 KB
testcase_46 AC 883 ms
49,112 KB
testcase_47 AC 894 ms
49,232 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(20);
        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<20;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<20;i++){
                if(Z&(1<<i)){
                    X=dp[X][i];
                }
            }
            Z=dist[x]-dist[Y]-1;
            for(int i=0;i<20;i++){
                if(Z&(1<<i)){
                    x=dp[x][i];
                }
            }
        }
        if(X==Y){
            return std::make_tuple(X,x,-1);
        }
        for(int i=19;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