結果

問題 No.898 tri-βutree
ユーザー niuezniuez
提出日時 2020-02-05 18:25:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 181 ms / 4,000 ms
コード長 3,768 bytes
コンパイル時間 1,178 ms
コンパイル使用メモリ 88,488 KB
実行使用メモリ 41,448 KB
最終ジャッジ日時 2024-11-08 23:22:13
合計ジャッジ時間 6,187 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
41,448 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 179 ms
26,244 KB
testcase_08 AC 166 ms
26,320 KB
testcase_09 AC 170 ms
26,320 KB
testcase_10 AC 169 ms
26,324 KB
testcase_11 AC 175 ms
26,324 KB
testcase_12 AC 173 ms
26,320 KB
testcase_13 AC 173 ms
26,316 KB
testcase_14 AC 173 ms
26,316 KB
testcase_15 AC 169 ms
26,324 KB
testcase_16 AC 169 ms
26,284 KB
testcase_17 AC 172 ms
26,308 KB
testcase_18 AC 181 ms
26,176 KB
testcase_19 AC 172 ms
26,304 KB
testcase_20 AC 172 ms
26,188 KB
testcase_21 AC 176 ms
26,420 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <set>
using namespace std;

struct union_find {
  vector<int> par;
  vector<int> rank;
  union_find(int n) : par(n) , rank(n) {
    for(int i = 0;i < n;i++) par[i] = i;
  }
  int root(int i) {
    return par[i] == i ? i : par[i] = root(par[i]);
  }
  /* unite x, y return parent */
  int unite(int x,int y) {
    x = root(x);
    y = root(y);
    if(x == y) return -1;
    if(rank[x] < rank[y]) {
      par[x] = y;
      return y;
    }
    else {
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
      return x;
    }
  }
};

using i64 = long long;
struct tarjans_offline_lca {
  using E = pair<int, i64>;
  vector<vector<E>> G;
  vector<int> ance;
  union_find uf;
  vector<i64> weight;
  vector<pair<int, int>> query;
  vector<vector<pair<int, int>>> q;
  vector<int> ans;
  tarjans_offline_lca(int n): G(n), ance(n), uf(n), weight(n), q(n) {}

  void add_edge(int a, int b, i64 w) {
    G[a].push_back({ b, w });
    G[b].push_back({ a, w });
  }
  void add_query(int a, int b) {
    int i = query.size();
    query.push_back({ a, b });
    q[a].push_back({ b, i });
    q[b].push_back({ a, i });
  }
  void dfs(int v, int f, i64 W) {
    ance[v] = v;
    weight[v] = W;
    for(auto e: G[v]) {
      int u = e.first;
      i64 w = e.second;
      if(f == u) continue;
      dfs(u, v, w + W);
      uf.unite(u, v);
      ance[uf.root(v)] = v;
    }
    for(auto e: q[v]) {
      int u = e.first;
      int i = e.second;
      if(ans[i] == -1) ans[i] = -2;
      else if(ans[i] == -2) ans[i] = ance[uf.root(u)];
    }
  }
  void offline_lca(int root) {
    ans.assign(query.size(), -1);
    dfs(root, -1, 0);
  }
};

#include <cstdio>

namespace niu {
  char cur;
  struct FIN {
    static inline bool is_blank(char c) { return c <= ' '; }
    inline char next() { return cur = getc_unlocked(stdin); }
    inline char peek() { return cur; }
    inline void skip() { while(is_blank(next())){} }
#define intin(inttype)  \
    FIN& operator>>(inttype& n) { \
      bool sign = 0; \
      n = 0; \
      skip(); \
      while(!is_blank(peek())) { \
        if(peek() == '-') sign = 1; \
        else n = (n << 1) + (n << 3) + (peek() & 0b1111); \
        next(); \
      } \
      if(sign) n = -n; \
      return *this; \
    }
intin(int)
intin(long long)
  } fin;

  char tmp[128];
  struct FOUT {
    static inline bool is_blank(char c) { return c <= ' '; }
    inline void push(char c) { putc_unlocked(c, stdout); }
    FOUT& operator<<(char c) { push(c); return *this; }
    FOUT& operator<<(const char* s) { while(*s) push(*s++); return *this; }
#define intout(inttype) \
    FOUT& operator<<(inttype n) { \
      if(n) { \
        char* p = tmp + 127; bool neg = 0; \
        if(n < 0) neg = 1, n = -n; \
        while(n) *--p = (n % 10) | 0b00110000, n /= 10; \
        if(neg) *--p = '-'; \
        return (*this) << p; \
      } \
      else { \
        push('0'); \
        return *this; \
      } \
    }
intout(int)
intout(long long)
  } fout;
}
#include <iostream>

int main() {
  using niu::fin;
  using niu::fout;
  i64 N;
  fin >> N;

  tarjans_offline_lca eul(N);
  for(int i = 0;i < N - 1;i++) {
    i64 a, b, c;
    niu::fin >> a >> b >> c;
    eul.add_edge(a, b, c);
  }

  i64 Q;
  fin >> Q;
  eul.query.reserve(Q);
  for(i64 q = 0; q < Q; q++) {
    i64 x, y, z;
    fin >> x >> y >> z;
    eul.add_query(x, y);
    eul.add_query(y, z);
    eul.add_query(x, z);
  }
  eul.offline_lca(0);

  auto dist = [&](i64 i) -> i64 {
    int a = eul.query[i].first;
    int b = eul.query[i].second;
    int c = eul.ans[i];
    return eul.weight[a] + eul.weight[b] - 2 * eul.weight[c];
  };
  for(i64 q = 0; q < Q; q++) {
    fout << (dist(q * 3) + dist(q * 3 + 1) + dist(q * 3 + 2)) / 2 << "\n";
  }
}
0