AtCoder Beginner Contest 014

Submission #1587312

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    const ll m = 30;
    ll n; cin >> n;
    vector<ll> h(n);
    vector<vector<ll>> par(m, vector<ll>(n));
    vector<vector<ll>> G(n);
    rep(i, n-1) {
        ll a, b; cin >> a >> b; --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    function<void(ll,ll,ll)> dfs = [&](ll v, ll pv, ll d) {
        h[v] = d;
        par[0][v] = pv;
        each(to, G[v]) {
            if (to == pv) continue;
            dfs(to, v, d+1);
        }
    };
    dfs(0, 0, 0);
    rep(i, 1, m) rep(j, n) {
        par[i][j] = par[i-1][par[i-1][j]];
    }
    auto lca = [&](ll a, ll b) {
        // 高さをあわせる
        if (h[a] > h[b]) swap(a, b);
        // cout << a << " " << b << endl;
        rrep(i, m) {
            if (h[b]-h[a] >= (1LL<<i)) {
                b = par[i][b];
            }
        }
        assert(h[a] == h[b]);
        // にぶたん
        rrep(i, m) {
            if (par[i][a] != par[i][b]) {
                a = par[i][a];
                b = par[i][b];
            }
        }
        assert(a != b);
        assert(par[0][a] == par[0][b]);
        return par[0][a];
    };
    ll Q; cin >> Q;
    rep(q, Q) {
        ll a, b; cin >> a >> b; --a, --b;
        cout << h[a] + h[b] - 2 * h[lca(a, b)] + 1 << endl;
    }
}

Submission

Task問題 D - 閉路
User nameユーザ名 drafear
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 2622 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
Subtask1 0 / 30 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt
Subtask2 0 / 70 subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample01.txt AC 1 ms 256 KB
subtask0_sample02.txt RE
subtask0_sample03.txt RE
subtask1_01.txt RE
subtask1_02.txt RE
subtask1_03.txt RE
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 2 ms 640 KB
subtask1_06.txt RE
subtask1_07.txt AC 56 ms 30704 KB
subtask1_08.txt AC 54 ms 30576 KB
subtask1_09.txt AC 57 ms 30576 KB
subtask1_10.txt AC 57 ms 30576 KB
subtask1_11.txt AC 57 ms 30576 KB
subtask1_12.txt AC 57 ms 30576 KB
subtask2_01.txt RE
subtask2_02.txt RE
subtask2_03.txt RE
subtask2_04.txt RE
subtask2_05.txt RE
subtask2_06.txt RE
subtask2_07.txt RE
subtask2_08.txt RE
subtask2_09.txt RE
subtask2_10.txt RE
subtask2_11.txt RE
subtask2_12.txt RE