結果

問題 No.1212 Second Path
ユーザー carrot46carrot46
提出日時 2020-08-31 17:50:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,385 bytes
コンパイル時間 2,000 ms
コンパイル使用メモリ 186,620 KB
実行使用メモリ 77,660 KB
最終ジャッジ日時 2024-11-16 10:40:57
合計ジャッジ時間 28,551 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 431 ms
64,636 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 161 ms
5,248 KB
testcase_24 AC 167 ms
5,248 KB
testcase_25 AC 175 ms
5,248 KB
testcase_26 AC 167 ms
5,248 KB
testcase_27 AC 187 ms
5,248 KB
testcase_28 AC 174 ms
5,248 KB
testcase_29 AC 563 ms
77,572 KB
testcase_30 AC 522 ms
77,660 KB
testcase_31 AC 551 ms
77,540 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 2 ms
5,248 KB
testcase_44 AC 1 ms
5,248 KB
testcase_45 AC 457 ms
64,504 KB
testcase_46 AC 477 ms
64,504 KB
testcase_47 AC 423 ms
64,500 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;
    }
};
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(lower_bound(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]].begin()) 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]].begin()) chmin(min_cost, ite->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