結果

問題 No.2337 Equidistant
ユーザー suisui
提出日時 2023-06-02 21:49:00
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,893 bytes
コンパイル時間 5,177 ms
コンパイル使用メモリ 272,104 KB
実行使用メモリ 33,444 KB
最終ジャッジ日時 2024-06-08 22:46:34
合計ジャッジ時間 21,213 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
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 AC 727 ms
33,444 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 783 ms
30,696 KB
testcase_25 WA -
testcase_26 AC 804 ms
30,464 KB
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i,a,b) for (int i = (int)(a) ; i < (int)(b+1); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define uni(v) v.erase(unique(v.begin(), v.end()), v.end());
using ll = long long;
using P = pair<int,int>;
using mint = modint998244353;
ostream& operator<< (ostream& os, const mint &x) {os << x.val(); return os;}
#ifdef LOCAL
    #include <debug.hpp>
    #define debug(...) debug::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
    #define debug(...) (static_cast<void>(0))
#endif

template <typename G> struct EulerTour {
  private:
    struct RMQ {
        int n, s;
        using P = std::pair<int, int>;
        std::vector<P> seg;
        P UNIT = P(1 << 30, -1);

        RMQ(int N) : n(N), s(1) {
        while (s < N) s <<= 1;
        seg.assign(2 * s, UNIT);
        }

        void set(int k, P x) { seg[k + s] = x; }

        P operator[](int k) const { return seg[k + s]; }

        void build() {
        for (int k = s - 1; k > 0; k--) {
            seg[k] = min(seg[2 * k], seg[2 * k + 1]);
        }
        }

        P query(int a, int b) const {
        P R = UNIT;
        for (a += s, b += s; a < b; a >>= 1, b >>= 1) {
            if (a & 1) R = min(R, seg[a++]);
            if (b & 1) R = min(R, seg[--b]);
        }
        return R;
        }

        int size() const { return n; }
    };

    std::vector<int> down, up;
    int id;
    RMQ rmq;

    void init(G &g, int root) {
        dfs(g, root, -1, 0);
        if (id < rmq.size()) rmq.set(id++, {-1, -1});
        for (int i = 0; i < (int)g.size(); i++) {
        if (down[i] == -1) {
            rmq.set(id++, {-1, -1});
            dfs(g, i, -1, 0);
            if (id < rmq.size()) rmq.set(id++, {-1, -1});
        }
        }
        rmq.build();
    }

    void dfs(G &g, int c, int p, int dp) {
        down[c] = id;
        rmq.set(id++, {dp, c});
        for (auto &d : g[c]) {
        if (d == p) continue;
        dfs(g, d, c, dp + 1);
        }
        up[c] = id;
        if (p != -1) rmq.set(id++, {dp - 1, p});
    }

  public:
    EulerTour(G &g, int root = 0)
        : down(g.size(), -1), up(g.size(), -1), id(0), rmq(2 * g.size()) {
        init(g, root);
    }

    std::pair<int, int> idx(int i) const { return {down[i], up[i]}; }

    int lca(int a, int b) const {
        if (down[a] > down[b]) std::swap(a, b);
        return rmq.query(down[a], down[b] + 1).second;
    }

    template <typename F>
    void node_query(int a, int b, const F &f) {
        int l = lca(a, b);
        f(down[l], down[a] + 1);
        f(down[l] + 1, down[b] + 1);
    }

    template <typename F>
    void edge_query(int a, int b, const F &f) {
        int l = lca(a, b);
        f(down[l] + 1, down[a] + 1);
        f(down[l] + 1, down[b] + 1);
    }

    template <typename F>
    void subtree_query(int a, const F &f) {
        f(down[a], up[a]);
    }

    int size() const { return int(rmq.size()); }
};

int main(){
    int n,q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    rep(_,n-1){
        int a,b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dist(n,-1);
    queue<int> que;
    dist[0] = 0;
    que.push(0);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int u:g[v]){
            if(dist[u]==-1){
                dist[u] = dist[v]+1;
                que.push(u);
            }
        }
    }
    EulerTour<vector<vector<int>>> et(g);
    debug(dist);
    rep(i,q){
        int s,t;
        cin >> s >> t;
        s--, t--;
        int lca = et.lca(s,t);
        int ans = dist[s]+dist[t]-2*dist[lca]-1;
        cout << ans%2 << endl;
    }
    return 0;
}
0