結果

問題 No.1212 Second Path
ユーザー carrot46carrot46
提出日時 2020-08-31 18:35:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 759 ms / 3,000 ms
コード長 4,390 bytes
コンパイル時間 2,794 ms
コンパイル使用メモリ 186,724 KB
実行使用メモリ 79,324 KB
最終ジャッジ日時 2024-11-16 20:49:12
合計ジャッジ時間 28,873 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 422 ms
79,324 KB
testcase_01 AC 666 ms
77,788 KB
testcase_02 AC 683 ms
76,000 KB
testcase_03 AC 712 ms
76,388 KB
testcase_04 AC 759 ms
72,412 KB
testcase_05 AC 743 ms
72,668 KB
testcase_06 AC 487 ms
64,504 KB
testcase_07 AC 589 ms
65,040 KB
testcase_08 AC 599 ms
65,172 KB
testcase_09 AC 559 ms
65,040 KB
testcase_10 AC 559 ms
65,168 KB
testcase_11 AC 565 ms
65,040 KB
testcase_12 AC 568 ms
65,056 KB
testcase_13 AC 564 ms
65,048 KB
testcase_14 AC 586 ms
65,044 KB
testcase_15 AC 590 ms
65,036 KB
testcase_16 AC 592 ms
65,048 KB
testcase_17 AC 414 ms
79,200 KB
testcase_18 AC 199 ms
5,248 KB
testcase_19 AC 198 ms
5,248 KB
testcase_20 AC 201 ms
5,248 KB
testcase_21 AC 190 ms
5,248 KB
testcase_22 AC 193 ms
5,248 KB
testcase_23 AC 176 ms
5,248 KB
testcase_24 AC 180 ms
5,248 KB
testcase_25 AC 177 ms
5,248 KB
testcase_26 AC 181 ms
5,248 KB
testcase_27 AC 183 ms
5,248 KB
testcase_28 AC 181 ms
5,248 KB
testcase_29 AC 588 ms
79,196 KB
testcase_30 AC 578 ms
79,200 KB
testcase_31 AC 604 ms
79,200 KB
testcase_32 AC 491 ms
49,052 KB
testcase_33 AC 438 ms
38,548 KB
testcase_34 AC 541 ms
61,084 KB
testcase_35 AC 253 ms
8,704 KB
testcase_36 AC 497 ms
51,180 KB
testcase_37 AC 478 ms
46,380 KB
testcase_38 AC 484 ms
49,020 KB
testcase_39 AC 394 ms
28,600 KB
testcase_40 AC 213 ms
5,248 KB
testcase_41 AC 491 ms
49,256 KB
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 2 ms
5,248 KB
testcase_44 AC 2 ms
5,248 KB
testcase_45 AC 466 ms
64,632 KB
testcase_46 AC 469 ms
64,668 KB
testcase_47 AC 469 ms
64,508 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int find_lca(int, int, ll&, ll&, vec&, std::vector<int>&, mat&, mat&, mat&, mat&, std::vector<std::vector<edge> >&)':
main.cpp:81:22: warning: 'temp_id' may be used uninitialized [-Wmaybe-uninitialized]
   81 |         id.push_back(temp_id);
      |                      ^~~~~~~
main.cpp:69:32: note: 'temp_id' was declared here
   69 |     int d = rank[y] - rank[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;

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, vector<int> &rank, vec &v_id, vec &v_len, vec &v_v, vector<ve> &G){
    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_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);
    }
}

int find_lca(int x, int y, ll &len, ll &min_cost, vec &id, vector<int> &rank, mat &dbl_v, mat &dbl_len, mat &dbl_id, mat &dbl_min, vector<ve> &G){
    if(rank[x] > rank[y]) swap(x, y);
    int d = rank[y] - rank[x], temp_id;
    Rrep(i, max_log) {
        if((d>>i)&1) {
            len += dbl_len[i][y];
            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]){
            len += dbl_len[i][x] + dbl_len[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];
        }
    }
    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;
    ++N;
    vector<ve> G(N, ve(0));
    make_G(G);
    rep(i,N) sort(ALL(G[i]));
    vector<int> rank(N, -1);
    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);
    reps(i, 1, max_log){
        rep(v, N){
            dbl_len[i][v] = min(dbl_len[i-1][v] + dbl_len[i-1][dbl_v[i-1][v]], INF);
            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, min_cost, id, rank, dbl_v, dbl_len, dbl_id, dbl_min, G);
        chmin(min_cost, dbl_len[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