AtCoder Beginner Contest 014

Submission #1590979

Source codeソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class EulerTour {
public:
  int N, k;
  vector<int> g[100001]; // maxの頂点数は適宜変更
  vector<int> vs, id, depth;
 
  EulerTour (int N) : N(N), k(0), vs(2 * N - 1), id(N, -1), depth(2 * N - 1) {}
  EulerTour () {}
 
  void Init(int n) {
      N = n;
      k = 0;
      vs.resize(2 * N - 1);
      id.resize(N, -1);
      depth.resize(2 * N - 1);
  }
 
  void AddEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
 
  // v : vertex, d : depth, k : num
  void Dfs(int v, int d, int &k) {
    id[v] = k;
    vs[k] = v;
    depth[k++] = d;
    int size_ = g[v].size();
 
    for (int i = 0; i < size_; ++i) {
      if (id[g[v][i]] == -1) {
          Dfs(g[v][i], d + 1, k);
          vs[k] = v;
          depth[k++] = d;
      }
    }
  }
 
  // 根は頂点0としている
  void Solve(int root = 0) {
    Dfs(root, 0, k);
  }
};
 
template <typename T>
class SegmentTree {
private:
  int n;
  T _init;
  vector<T> seg;
 
  int size (int N) {
    int ret;
    for (ret = 1; ret < N; ret <<= 1);
    return ret;
  }
 
  T query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return _init;
    if (a <= l and r <= b) return seg[k];
 
    T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
 
public:
  SegmentTree (int N, T i = 0) : n(size(N)), seg(size(N) * 2, i), _init(i) {}
  SegmentTree () {}
 
  void Init(int N, T i) {
      n = size(N);
      seg.resize(size(N) * 2 - 1, i);
      _init = i;
  }
 
  void Update (int k, T val) {
    k += n - 1;
    seg[k] = val;
    while (k > 0) {
      k = (k - 1) / 2;
      // 適宜変更
      seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }
 
  // [l, r) 開区間であることに注意!!! ... [l, r]ならfind(l, r + 1)
  T Find(int l, int r) {
    return query(l, r, 0, 0, n);
  }
};
 
class LCA {
public:
    int N;
    EulerTour etour;
    SegmentTree<pair<int, int> > segtree;
 
    LCA() {}
    LCA(int N) : N(N), etour(N) {}
 
    void Init(int N) {
        etour.Init(N);
    }
 
    void AddEdge(int u, int v) {
        etour.AddEdge(u, v);
    }
 
    // LCA求める前の下準備
    void Preparation() {
        etour.Solve();
        segtree.Init(etour.k, {int(1e9+7), int(1e9+7)});
        for (int i = 0; i < etour.k; ++i) segtree.Update(i, {etour.depth[i], i});
    }
 
    int Lca(int a, int b) {
        if (etour.id[a] > etour.id[b]) swap(a, b);
        pair<int, int> lca = segtree.Find(etour.id[a], etour.id[b] + 1);
        return etour.vs[lca.second];
    }

    int Solve(int a, int b) {
        if (etour.id[a] > etour.id[b]) swap(a, b);
        int lca = Lca(a, b), da, db, dc;
        da = etour.depth[etour.id[a]];
        db = etour.depth[etour.id[b]];
        dc = etour.depth[etour.id[lca]];
        return (da + db - 2 * dc + 1);
    }
 
};
 
int N, x, y, q, a, b;
LCA lca;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    lca.Init(N);
    for (int i = 0; i < N - 1; ++i) {
        cin >> x >> y;
        x--, y--;
        lca.AddEdge(x, y);
    }
 
    lca.Preparation();
 
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> a >> b;
        a--, b--;
        cout << lca.Solve(a, b) << endl;
    }
    return 0;
}

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
Subtask1 30 / 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 70 / 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 2 ms 2560 KB
subtask0_sample02.txt AC 2 ms 2560 KB
subtask0_sample03.txt AC 2 ms 2560 KB
subtask1_01.txt AC 45 ms 15488 KB
subtask1_02.txt AC 45 ms 15488 KB
subtask1_03.txt AC 2 ms 2560 KB
subtask1_04.txt AC 2 ms 2560 KB
subtask1_05.txt AC 3 ms 2688 KB
subtask1_06.txt AC 3 ms 2688 KB
subtask1_07.txt AC 61 ms 11904 KB
subtask1_08.txt AC 54 ms 11904 KB
subtask1_09.txt AC 53 ms 11776 KB
subtask1_10.txt AC 58 ms 11776 KB
subtask1_11.txt AC 56 ms 11904 KB
subtask1_12.txt AC 55 ms 11776 KB
subtask2_01.txt AC 227 ms 16128 KB
subtask2_02.txt AC 243 ms 16000 KB
subtask2_03.txt AC 178 ms 2816 KB
subtask2_04.txt AC 201 ms 2816 KB
subtask2_05.txt AC 219 ms 2944 KB
subtask2_06.txt AC 220 ms 3072 KB
subtask2_07.txt AC 310 ms 12160 KB
subtask2_08.txt AC 320 ms 12160 KB
subtask2_09.txt AC 317 ms 12160 KB
subtask2_10.txt AC 307 ms 12160 KB
subtask2_11.txt AC 336 ms 12160 KB
subtask2_12.txt AC 309 ms 12288 KB