結果

問題 No.1212 Second Path
ユーザー penguinmanpenguinman
提出日時 2020-07-31 00:41:39
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,194 ms / 3,000 ms
コード長 5,425 bytes
コンパイル時間 3,785 ms
コンパイル使用メモリ 206,384 KB
実行使用メモリ 108,856 KB
最終ジャッジ日時 2023-08-05 05:40:08
合計ジャッジ時間 29,439 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 361 ms
103,560 KB
testcase_01 AC 881 ms
102,116 KB
testcase_02 AC 717 ms
93,692 KB
testcase_03 AC 733 ms
95,336 KB
testcase_04 AC 816 ms
76,136 KB
testcase_05 AC 741 ms
76,600 KB
testcase_06 AC 1,058 ms
52,348 KB
testcase_07 AC 529 ms
41,580 KB
testcase_08 AC 584 ms
41,768 KB
testcase_09 AC 599 ms
41,440 KB
testcase_10 AC 564 ms
42,016 KB
testcase_11 AC 539 ms
41,508 KB
testcase_12 AC 547 ms
41,692 KB
testcase_13 AC 528 ms
41,432 KB
testcase_14 AC 575 ms
41,556 KB
testcase_15 AC 621 ms
42,044 KB
testcase_16 AC 530 ms
41,792 KB
testcase_17 AC 351 ms
102,464 KB
testcase_18 AC 66 ms
8,632 KB
testcase_19 AC 66 ms
8,952 KB
testcase_20 AC 67 ms
8,832 KB
testcase_21 AC 65 ms
9,360 KB
testcase_22 AC 67 ms
9,208 KB
testcase_23 AC 37 ms
7,160 KB
testcase_24 AC 47 ms
7,320 KB
testcase_25 AC 44 ms
7,252 KB
testcase_26 AC 48 ms
7,388 KB
testcase_27 AC 48 ms
7,704 KB
testcase_28 AC 49 ms
8,036 KB
testcase_29 AC 615 ms
108,856 KB
testcase_30 AC 710 ms
108,788 KB
testcase_31 AC 631 ms
108,724 KB
testcase_32 AC 408 ms
33,796 KB
testcase_33 AC 333 ms
27,724 KB
testcase_34 AC 477 ms
39,876 KB
testcase_35 AC 131 ms
12,500 KB
testcase_36 AC 424 ms
34,744 KB
testcase_37 AC 400 ms
32,540 KB
testcase_38 AC 410 ms
33,764 KB
testcase_39 AC 308 ms
23,108 KB
testcase_40 AC 84 ms
9,968 KB
testcase_41 AC 495 ms
34,164 KB
testcase_42 AC 2 ms
4,376 KB
testcase_43 AC 2 ms
4,376 KB
testcase_44 AC 2 ms
4,376 KB
testcase_45 AC 1,194 ms
52,148 KB
testcase_46 AC 1,059 ms
52,216 KB
testcase_47 AC 1,025 ms
52,216 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