結果

問題 No.1212 Second Path
ユーザー carrot46carrot46
提出日時 2020-09-01 12:04:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 694 ms / 3,000 ms
コード長 4,010 bytes
コンパイル時間 2,241 ms
コンパイル使用メモリ 186,240 KB
実行使用メモリ 63,328 KB
最終ジャッジ日時 2024-11-18 11:16:57
合計ジャッジ時間 30,216 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 394 ms
63,268 KB
testcase_01 AC 643 ms
62,236 KB
testcase_02 AC 670 ms
60,700 KB
testcase_03 AC 662 ms
60,956 KB
testcase_04 AC 694 ms
57,892 KB
testcase_05 AC 692 ms
58,144 KB
testcase_06 AC 476 ms
51,692 KB
testcase_07 AC 544 ms
52,256 KB
testcase_08 AC 590 ms
52,132 KB
testcase_09 AC 560 ms
52,256 KB
testcase_10 AC 543 ms
52,256 KB
testcase_11 AC 554 ms
52,128 KB
testcase_12 AC 617 ms
52,256 KB
testcase_13 AC 546 ms
52,256 KB
testcase_14 AC 552 ms
52,256 KB
testcase_15 AC 553 ms
52,132 KB
testcase_16 AC 552 ms
52,128 KB
testcase_17 AC 396 ms
63,136 KB
testcase_18 AC 229 ms
47,908 KB
testcase_19 AC 231 ms
47,780 KB
testcase_20 AC 228 ms
47,776 KB
testcase_21 AC 226 ms
47,776 KB
testcase_22 AC 227 ms
47,776 KB
testcase_23 AC 206 ms
47,780 KB
testcase_24 AC 211 ms
47,776 KB
testcase_25 AC 208 ms
47,776 KB
testcase_26 AC 214 ms
47,904 KB
testcase_27 AC 214 ms
47,772 KB
testcase_28 AC 214 ms
47,732 KB
testcase_29 AC 569 ms
63,328 KB
testcase_30 AC 569 ms
63,132 KB
testcase_31 AC 572 ms
63,264 KB
testcase_32 AC 499 ms
50,848 KB
testcase_33 AC 458 ms
50,080 KB
testcase_34 AC 540 ms
51,876 KB
testcase_35 AC 286 ms
47,904 KB
testcase_36 AC 507 ms
50,848 KB
testcase_37 AC 478 ms
50,720 KB
testcase_38 AC 475 ms
50,848 KB
testcase_39 AC 420 ms
49,056 KB
testcase_40 AC 240 ms
47,776 KB
testcase_41 AC 496 ms
50,788 KB
testcase_42 AC 36 ms
47,780 KB
testcase_43 AC 37 ms
47,776 KB
testcase_44 AC 36 ms
47,776 KB
testcase_45 AC 465 ms
51,692 KB
testcase_46 AC 456 ms
51,692 KB
testcase_47 AC 451 ms
51,696 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int find_lca(int, int, ll&, vec&)':
main.cpp:85:22: warning: 'temp_id' may be used uninitialized [-Wmaybe-uninitialized]
   85 |         id.push_back(temp_id);
      |                      ^~~~~~~
main.cpp:74:34: note: 'temp_id' was declared here
   74 |     int d = depth[y] - depth[x], temp_id;
      |                                  ^~~~~~~

ソースコード

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, INF)), 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)));
        dbl_id[0][e.to] = i;
        len[e.to] = len[v] + e.cost;
        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;
    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];
            auto ite = G[y].begin() + (temp_id == 0);
            if(ite != G[y].end()) chmin(min_cost, ite->cost);
        }
    }
    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]));
            auto ite = G[dbl_v[i][x]].begin() + (dbl_id[i][x] == 0);
            if(ite != G[dbl_v[i][x]].end()) chmin(min_cost, ite->cost);
            auto ite2 = G[dbl_v[i][y]].begin() + (dbl_id[i][y] == 0);
            if(ite2 != G[dbl_v[i][y]].end()) chmin(min_cost, ite2->cost);
            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]];
            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, 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