結果

問題 No.1212 Second Path
ユーザー penguinmanpenguinman
提出日時 2020-07-30 22:56:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,423 bytes
コンパイル時間 2,598 ms
コンパイル使用メモリ 208,176 KB
実行使用メモリ 110,420 KB
最終ジャッジ日時 2024-10-15 03:25:15
合計ジャッジ時間 21,439 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 314 ms
105,172 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 298 ms
104,088 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 37 ms
7,312 KB
testcase_24 WA -
testcase_25 AC 40 ms
7,336 KB
testcase_26 AC 48 ms
7,400 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 455 ms
110,240 KB
testcase_30 AC 452 ms
110,420 KB
testcase_31 AC 466 ms
110,420 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 2 ms
5,248 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
権限があれば一括ダウンロードができます

ソースコード

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,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