結果

問題 No.1212 Second Path
ユーザー carrot46
提出日時 2020-09-01 12:13:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 622 ms / 3,000 ms
コード長 3,588 bytes
コンパイル時間 2,357 ms
コンパイル使用メモリ 186,008 KB
実行使用メモリ 61,728 KB
最終ジャッジ日時 2024-11-18 11:47:30
合計ジャッジ時間 26,328 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}

struct edge{
    int to;
    ll cost;
    edge(){}
    edge(int a, ll b){
        to = a;
        cost = b;
    }
    bool operator < (const edge &e){
        return cost < e.cost;
    }
    bool operator == (const edge &e){
        return cost == e.cost && to == e.to;
    }
};
using ve = vector<edge>;
const int max_log = 17, max_N = (int)1e+5 + 1;

vector<ve> G(max_N, ve(0));
vec depth(max_N, -1), len(max_N, 0);
mat dbl_min(max_log, vec(max_N)), dbl_v(max_log, vec(max_N)), dbl_id(max_log, vec(max_N));

void make_G(vector<ve> &G){
    rep(i,N - 2){
        int u, v, w;
        cin>>u>>v>>w;
        --u; --v;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    G[N - 1].emplace_back(0, INF);
}

void dfs(int v, int p){
    depth[v] = depth[p] + 1;
    rep(i, (int)G[v].size()) {
        edge e = G[v][i];
        G[e.to].erase(find(ALL(G[e.to]), edge(v, e.cost)));
        len[e.to] = len[v] + e.cost;
        auto ite = G[v].begin() + (i == 0);
        dbl_min[0][e.to] = (ite == G[v].end() ? INF : ite->cost);
        dbl_id[0][e.to] = i;
        dbl_v[0][e.to] = v;
        dfs(e.to, v);
    }
}

int find_lca(int x, int y, ll &min_cost, vec &id){
    if(depth[x] > depth[y]) swap(x, y);
    int d = depth[y] - depth[x], temp_id(-1);
    Rrep(i, max_log) {
        if((d>>i)&1) {
            chmin(min_cost, dbl_min[i][y]);
            temp_id = dbl_id[i][y];
            y = dbl_v[i][y];
        }
    }
    if(x == y) {
        id.push_back(temp_id);
        return x;
    }
    Rrep(i, max_log){
        if(dbl_v[i][x] != dbl_v[i][y]){
            chmin(min_cost, min(dbl_min[i][x], dbl_min[i][y]));
            x = dbl_v[i][x];
            y = dbl_v[i][y];
        }
    }
    id.push_back(dbl_id[0][x]);  id.push_back(dbl_id[0][y]);
    return dbl_v[0][x];
}

int main() {
    cin>>N;
    ++N;
    make_G(G);
    rep(i,N) sort(ALL(G[i]));
    depth[N - 1] = 0;
    len[N - 1] = -INF;
    len[0] = 0;
    dbl_id[0][0] = 0;
    dbl_v[0][0] = dbl_v[0][N - 1] = N - 1;
    dfs(0, (int)N - 1);
    reps(i, 1, max_log){
        rep(v, N){
            dbl_v[i][v] = dbl_v[i-1][dbl_v[i-1][v]];
            dbl_id[i][v] = dbl_id[i-1][dbl_v[i-1][v]];
            dbl_min[i][v] = min(dbl_min[i-1][v], dbl_min[i-1][dbl_v[i-1][v]]);
        }
    }

    cin>>Q;
    rep(_, Q) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        ll res, min_cost(INF);
        vec id(0);
        int lca = find_lca(x, y, min_cost, id);
        res = len[x] + len[y] - len[lca] * 2;
        chmin(min_cost, len[lca] - len[dbl_v[0][lca]]);
        if (y != lca) swap(x, y);
        if (!G[x].empty()) chmin(min_cost, G[x][0].cost);
        if (!G[y].empty() && id.size() == 2) chmin(min_cost, G[y][0].cost);
        rep(i, (int) G[lca].size()) {
            if(find(ALL(id), i) == id.end()) {
                chmin(min_cost, G[lca][i].cost);
                break;
            }
        }

        cout << (min_cost == INF ? -1 : res + min_cost * 2) << endl;
    }
}
0