結果

問題 No.1212 Second Path
コンテスト
ユーザー carrot46
提出日時 2020-08-31 17:13:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,917 bytes
コンパイル時間 2,242 ms
コンパイル使用メモリ 189,140 KB
実行使用メモリ 64,860 KB
最終ジャッジ日時 2024-11-16 05:57:52
合計ジャッジ時間 25,383 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 25 RE * 15
権限があれば一括ダウンロードができます

ソースコード

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, cost;
    edge(){}
    edge(int a, int b){
        to = a;
        cost = b;
    }
    bool operator < (const edge &e){
        return cost < e.cost;
    }
    bool operator == (const edge &e){
        return cost = e.cost;
    }
};
using ve = vector<edge>;
const int max_log = 17;

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

void dfs(int v, int p, vector<int> &rank, vec &v_id, vec &v_len, vec &v_v, vector<ve> &G, vec &v_parent_cost){
    rank[v] = rank[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)));
        v_parent_cost[e.to] = e.cost;
        v_id[e.to] = i;
        v_len[e.to] = e.cost;
        v_v[e.to] = v;
        dfs(e.to, v, rank, v_id, v_len, v_v, G, v_parent_cost);
    }
}

int find_lca(int x, int y, ll &len, vec &id, vector<int> &rank, mat &dbl_v, mat &dbl_len, mat &dbl_id){
    if(rank[x] > rank[y]) swap(x, y);
    int d = rank[y] - rank[x], temp_id(-1);
    Rrep(i, max_log) {
        if((d>>i)&1) {
            len += dbl_len[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]){
            len += dbl_len[i][x] + dbl_len[i][y];
            x = dbl_v[i][x];
            y = dbl_v[i][y];
        }
    }
    len += dbl_len[0][x] + dbl_len[0][y];
    id.push_back(dbl_id[0][x]);  id.push_back(dbl_id[0][y]);
    return dbl_v[0][x];
}

int main() {
    cin>>N;
    vector<ve> G(N + 1, ve(0));
    make_G(G);
    ++N;
    rep(i,N) sort(ALL(G[i]));
    vector<int> rank(N, -1);
    vec parent_cost(N, INF);
    mat dbl_min(max_log, vec(N, INF)), dbl_len(max_log, vec(N)), dbl_v(max_log, vec(N)), dbl_id(max_log, vec(N));
    rank[N - 1] = 0;
    dbl_id[0][0] = 0;
    dbl_len[0][0] = INF;
    dbl_v[0][0] = dbl_v[0][N - 1] = N - 1;
    dfs(0, (int)N - 1, rank, dbl_id[0], dbl_len[0], dbl_v[0], G, parent_cost);
    reps(i, 1, max_log){
        rep(v, N){
            dbl_len[i][v] = dbl_len[i-1][v] + dbl_len[i-1][dbl_v[i-1][v]];
            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]];
            auto ite = G[dbl_v[i-1][v]].begin() + (int)(dbl_id[i-1][v] == 0);
            dbl_min[i][v] = min({dbl_min[i-1][v], dbl_min[i-1][dbl_v[i-1][v]], ite == G[dbl_v[i-1][v]].end() ? INF : ite->cost});
        }
    }

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