結果

問題 No.1212 Second Path
ユーザー penguinmanpenguinman
提出日時 2020-08-08 18:05:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 707 ms / 3,000 ms
コード長 5,970 bytes
コンパイル時間 2,731 ms
コンパイル使用メモリ 209,320 KB
実行使用メモリ 106,148 KB
最終ジャッジ日時 2024-10-15 03:31:13
合計ジャッジ時間 21,008 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 285 ms
100,776 KB
testcase_01 AC 528 ms
99,496 KB
testcase_02 AC 513 ms
91,048 KB
testcase_03 AC 554 ms
92,676 KB
testcase_04 AC 482 ms
73,384 KB
testcase_05 AC 506 ms
74,024 KB
testcase_06 AC 685 ms
50,072 KB
testcase_07 AC 354 ms
38,992 KB
testcase_08 AC 363 ms
39,000 KB
testcase_09 AC 372 ms
38,996 KB
testcase_10 AC 365 ms
39,380 KB
testcase_11 AC 358 ms
38,860 KB
testcase_12 AC 375 ms
38,992 KB
testcase_13 AC 365 ms
38,996 KB
testcase_14 AC 361 ms
39,020 KB
testcase_15 AC 372 ms
39,404 KB
testcase_16 AC 357 ms
38,996 KB
testcase_17 AC 290 ms
99,884 KB
testcase_18 AC 53 ms
8,784 KB
testcase_19 AC 60 ms
9,136 KB
testcase_20 AC 56 ms
9,048 KB
testcase_21 AC 57 ms
9,540 KB
testcase_22 AC 57 ms
9,468 KB
testcase_23 AC 32 ms
7,188 KB
testcase_24 AC 42 ms
7,524 KB
testcase_25 AC 39 ms
7,336 KB
testcase_26 AC 42 ms
7,532 KB
testcase_27 AC 42 ms
7,832 KB
testcase_28 AC 43 ms
7,896 KB
testcase_29 AC 418 ms
106,024 KB
testcase_30 AC 418 ms
106,148 KB
testcase_31 AC 422 ms
106,148 KB
testcase_32 AC 294 ms
32,060 KB
testcase_33 AC 232 ms
26,440 KB
testcase_34 AC 335 ms
37,340 KB
testcase_35 AC 104 ms
12,500 KB
testcase_36 AC 292 ms
32,936 KB
testcase_37 AC 266 ms
30,928 KB
testcase_38 AC 281 ms
31,796 KB
testcase_39 AC 200 ms
22,136 KB
testcase_40 AC 72 ms
10,076 KB
testcase_41 AC 287 ms
32,364 KB
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 1 ms
5,248 KB
testcase_44 AC 2 ms
5,248 KB
testcase_45 AC 704 ms
50,044 KB
testcase_46 AC 704 ms
50,076 KB
testcase_47 AC 707 ms
49,940 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);
        }
    }
    if(data.empty()) data.push_back(inf);
    for(auto p:memo[now]){
        int X,Y,Z; std::tie(X,Y,Z)=p;
        if(X>=0){
            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]]++;
        }
    }
}
struct Union_Find{
    int N;
    vector<int> par;
    Union_Find(int n):N(n){
        par.resize(N);
        for(int i=0;i<N;i++) par[i]=i;
    }
    int root(int X){
        if(par[X]==X) return X;
        return par[X]=root(par[X]);
    }
    bool same(int X,int Y){
        return root(X)==root(Y);
    }
    void unite(int X,int Y){
        X=root(X),Y=root(Y);
        if(X!=Y) par[X]=Y;
    }
};
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(2<=N&&N<=MAX);
    Union_Find UF(N);
    vector<vector<int>> edge(N),weight(N);
    for(int i=1;i<N;i++){
        int X,Y,Z; cin>>X>>Y>>Z;
        assert(X!=Y&&1<=X&&X<=N&&1<=Y&&Y<=N&&1<=Z&&Z<=INF);
        UF.unite(X-1,Y-1);
        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);
    }
    bool flag=1;
    for(int i=1;i<N;i++){
        flag&=UF.same(1,i);
    }
    assert(flag);
    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(X!=Y&&1<=X&&X<=N&&1<=Y&&Y<=N);
        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