結果

問題 No.1212 Second Path
ユーザー SHIJOUSHIJOU
提出日時 2020-09-04 15:27:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 894 ms / 3,000 ms
コード長 5,912 bytes
コンパイル時間 3,414 ms
コンパイル使用メモリ 231,760 KB
実行使用メモリ 211,696 KB
最終ジャッジ日時 2024-05-04 11:00:55
合計ジャッジ時間 30,086 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 403 ms
209,408 KB
testcase_01 AC 754 ms
208,000 KB
testcase_02 AC 786 ms
203,496 KB
testcase_03 AC 842 ms
204,472 KB
testcase_04 AC 805 ms
194,576 KB
testcase_05 AC 894 ms
194,860 KB
testcase_06 AC 488 ms
178,316 KB
testcase_07 AC 655 ms
177,732 KB
testcase_08 AC 578 ms
177,868 KB
testcase_09 AC 562 ms
177,712 KB
testcase_10 AC 540 ms
177,904 KB
testcase_11 AC 558 ms
177,792 KB
testcase_12 AC 562 ms
177,780 KB
testcase_13 AC 569 ms
177,812 KB
testcase_14 AC 555 ms
177,808 KB
testcase_15 AC 558 ms
177,860 KB
testcase_16 AC 552 ms
177,796 KB
testcase_17 AC 380 ms
208,900 KB
testcase_18 AC 206 ms
166,068 KB
testcase_19 AC 215 ms
166,132 KB
testcase_20 AC 215 ms
166,156 KB
testcase_21 AC 218 ms
166,328 KB
testcase_22 AC 209 ms
166,180 KB
testcase_23 AC 172 ms
165,784 KB
testcase_24 AC 189 ms
166,144 KB
testcase_25 AC 187 ms
166,004 KB
testcase_26 AC 186 ms
166,228 KB
testcase_27 AC 191 ms
166,036 KB
testcase_28 AC 187 ms
166,044 KB
testcase_29 AC 561 ms
211,696 KB
testcase_30 AC 574 ms
211,588 KB
testcase_31 AC 580 ms
211,584 KB
testcase_32 AC 467 ms
174,604 KB
testcase_33 AC 412 ms
172,556 KB
testcase_34 AC 514 ms
176,912 KB
testcase_35 AC 271 ms
166,824 KB
testcase_36 AC 471 ms
174,916 KB
testcase_37 AC 456 ms
174,208 KB
testcase_38 AC 475 ms
174,484 KB
testcase_39 AC 384 ms
170,624 KB
testcase_40 AC 235 ms
166,192 KB
testcase_41 AC 494 ms
174,608 KB
testcase_42 AC 135 ms
162,048 KB
testcase_43 AC 140 ms
161,920 KB
testcase_44 AC 140 ms
162,048 KB
testcase_45 AC 413 ms
178,320 KB
testcase_46 AC 423 ms
178,316 KB
testcase_47 AC 421 ms
178,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

template<class T>
struct lca {
  int n, root, l;
  vector<vector<int> > to, par;
  vector<vector<T> > co;
  vector<int> dep;
  vector<T> costs;
  lca(int n):n(n), to(n), co(n), dep(n), costs(n) {
    l = 0;
    while((1<<l) < n) ++l;
    par = vector<vector<int> >(n+1, vector<int>(l, n));
  }
  void add(int a, int b, T c=0) {
    to[a].push_back(b); co[a].push_back(c);
    to[b].push_back(a); co[b].push_back(c);
  }
  void dfs(int v, int d=0, T c=0, int p=-1) {
    if(p != -1) par[v][0] = p;
    dep[v] = d;
    costs[v] = c;
    for(int i = 0; i < to[v].size(); ++i) {
      int u = to[v][i];
      if(u == p) continue;
      dfs(u, d+1, c+co[v][i], v);
    }
  }
  void init(int _root=0) {
    root = _root;
    dfs(root);
    for(int i = 0; i < l-1; ++i) {
      for(int v = 0; v < n; ++v) {
        par[v][i+1] = par[par[v][i]][i];
      }
    }
  }
  int lca_(int a, int b) {
    if(dep[a] > dep[b]) swap(a, b);
    int gap = dep[b]-dep[a];
    for(int i = l-1; i >= 0; --i) {
      int len = 1<<i;
      if(gap >= len) {
        gap -= len;
        b = par[b][i];
      }
    }
    if(a == b) return a;
    for(int i = l-1; i >= 0; --i) {
      int na = par[a][i];
      int nb = par[b][i];
      if(na != nb) {
        a = na;
        b = nb;
      }
    }
    return par[a][0];
  }
  int length(int a, int b) {
    int c = lca_(a, b);
    return dep[a]+dep[b]-dep[c]*2;
  }
  T dist(int a, int b) {
    int c = lca_(a, b);
    return costs[a]+costs[b]-costs[c]*2;
  }
};

template<class T>
struct SegTree {
  using FX = function<T(T, T)>;
  int n;
  FX fx;
  const T ex;
  vector<T> dat;
  SegTree(int n_, FX fx_, T ex_):fx(fx_), ex(ex_), n(1) {
    while(n < n_) n <<= 1;
    dat.assign((n<<1)-1, ex);
  }
  inline int chld(int k) {return (k<<1)+1;}
  inline int chrd(int k) {return (k<<1)+2;}
  void update(int i, T x) {
    i += n-1;
    dat[i] = x;
    while(i) {
      i = (i-1)>>1;
      dat[i] = fx(dat[chld(i)], dat[chrd(i)]);
    }
  }
  inline T query(int a, int b) {return query(a, b, 0, 0, n);}
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return ex;
    if(a <= l && r <= b) return dat[k];
    T vl = query(a, b, chld(k), l, (l+r)>>1);
    T vr = query(a, b, chrd(k), (l+r)>>1, r);
    return fx(vl, vr);
  }
  const T &operator[](int idx) const {return dat[idx+n-1];}
};

struct edge {
  int to, cost;
};
#define N 100100

//head

int n;
vector<edge> G[N];
int q;
int x[N], y[N], z[N];
vi dat1[N];
vector<P> dat2[N];
queue<int> info1[N], info2[N];
lca<ll> L(N);
SegTree<int> rng(N, [](const int i, const int j)->int{return min(i, j);}, 0x7fffffff);

void dfs(int i=0, int j=-1) {
  list<P> lst;
  for(edge &e:G[i]) {
    int ne = e.to;
    list<P>::iterator itr = lst.begin();
    while(true) {
      if(itr == lst.end()) {
        if(lst.size() < 3) {
          lst.emplace_back(e.cost, ne);
        }
        break;
      }
      if(itr->first > e.cost) {
        lst.emplace(itr, e.cost, ne);
        if(lst.size() > 3) lst.pop_back();
        break;
      }
      itr = next(itr);
    }
  }
  while(lst.size() < 3) lst.emplace_back(0x7fffffff, -10);
  for(edge &e:G[i]) {
    int ne = e.to;
    if(ne == j) continue;
    list<P>::iterator itr = lst.begin();
    while(itr->second == j or itr->second == ne) itr = next(itr);
    rng.update(L.dep[i], itr->first);
    dfs(ne, i);
  }
  for(int x:dat1[i]) {
    if(x == i) {
      info1[i].emplace(0x7fffffff);
      continue;
    }
    list<P>::iterator itr = lst.begin();
    while(itr->second == j) itr = next(itr);
    if(L.dep[i]-1 == L.dep[x]) {
      info1[i].emplace(itr->first);
    }
    else {
      info1[i].emplace(min(itr->first, rng.query(L.dep[x]+1, L.dep[i])));
    }
  }
  for(P x:dat2[i]) {
    list<P>::iterator itr = lst.begin();
    while(true) {
      if(itr->second == -10) break;
      int u = L.lca_(x.first, itr->second);
      int v = L.lca_(x.second, itr->second);
      if((u != i and u != j) or (v != i and v != j)) {
        itr = next(itr);
        continue;
      }
      break;
    }
    info2[i].emplace(itr->first);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  rep(i, n-1) {
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;
    L.add(u, v, w);
    G[u].emplace_back((edge){v, w});
    G[v].emplace_back((edge){u, w});
  }
  L.init();
  cin >> q;
  rep(i, q) {
    cin >> x[i] >> y[i];
    x[i]--; y[i]--;
    z[i] = L.lca_(x[i], y[i]);
    dat1[x[i]].emplace_back(z[i]);
    dat1[y[i]].emplace_back(z[i]);
    dat2[z[i]].emplace_back(x[i], y[i]);
  }
  dfs();
  rep(i, q) {
    //cout << P(info1[x[i]].front(), info1[y[i]].front()) << ' ' << info2[z[i]].front() << endl;
    int u = min({info1[x[i]].front(), info1[y[i]].front(), info2[z[i]].front()});
    info1[x[i]].pop();
    info1[y[i]].pop();
    info2[z[i]].pop();
    if(u == 0x7fffffff) cout << "-1\n";
    else cout << u*2+L.dist(x[i], y[i]) << '\n';
    //cout << L.dist(x[i], y[i]) << "\n\n";
  }
}
0