結果

問題 No.1212 Second Path
コンテスト
ユーザー msm1993
提出日時 2020-10-08 10:19:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 329 ms / 3,000 ms
コード長 3,865 bytes
コンパイル時間 1,170 ms
コンパイル使用メモリ 105,384 KB
実行使用メモリ 58,240 KB
最終ジャッジ日時 2024-07-20 05:51:24
合計ジャッジ時間 14,842 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 1212.cc:  No.1212 Second Path - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int BN = 17;
const int INF = 1 << 30;

/* typedef */

typedef long long ll;
typedef queue<int> qi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

struct Edge {
  ll sum;
  int cw, mw0, mw1;
  bool mwb;
  Edge(): sum(0), cw(INF), mw0(INF), mw1(INF), mwb(false) {}
  Edge(ll _sum, int _cw, int _mw0, int _mw1, bool _mwb):
    sum(_sum), cw(_cw), mw0(_mw0), mw1(_mw1), mwb(_mwb) {}

  Edge operator+(const Edge &ev) {
    Edge r;
    r.sum = sum + ev.sum;
    r.cw = ev.cw;

    if (ev.mwb && ev.mw0 == cw) { // not use ev.mw0
      if (mw0 < ev.mw1) {
	r.mw0 = mw0, r.mwb = mwb;
	r.mw1 = min(mw1, ev.mw1);
      }
      else {
	r.mw0 = ev.mw1, r.mwb = false;
	r.mw1 = mw0;
      }
    }
    else {
      if (mw0 < ev.mw0) {
	r.mw0 = mw0, r.mwb = mwb;
	r.mw1 = min(mw1, ev.mw0);
      }
      else {
	r.mw0 = ev.mw0, r.mwb = false;
	r.mw1 = min(mw0, ev.mw1);
      }
    }

    return r;
  }
};

/* global variables */

vpii nbrs[MAX_N];
int ps[MAX_N][BN], ds[MAX_N], cns[MAX_N], mcws[MAX_N][3];
Edge es[MAX_N][BN];

/* subroutines */

inline void setmcw(int mcw[], int w) {
  for (int i = 0; i < 3; i++)
    if (mcw[i] > w) {
      for (int j = 2; j > i; j--) mcw[j] = mcw[j - 1];
      mcw[i] = w;
      break;
    }
}

inline int getmcw(int mcw[], int w0, int w1 = INF) {
  if (mcw[0] != w0) return mcw[0];
  if (mcw[1] != w1) return mcw[1];
  return mcw[2];
}

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 1; i < n; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--, v--;
    nbrs[u].push_back(pii(v, w));
    nbrs[v].push_back(pii(u, w));
  }

  ps[0][0] = -1, ds[0] = 0;
  qi q;
  q.push(0);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    fill(mcws[u], mcws[u] + 3, INF);

    int up = ps[u][0], vd = ds[u] + 1;
    vpii &nbru = nbrs[u];
    for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int v = vit->first;
      if (v != up) {
	ps[v][0] = u, ds[v] = vd;
	es[v][0].sum = es[v][0].cw = vit->second;
	setmcw(mcws[u], vit->second);

	cns[u]++;
	q.push(v);
      }
    }
  }

  for (int u = 0; u < n; u++) {
    es[u][0].mw0 = mcws[u][0], es[u][0].mwb = true;
    es[u][0].mw1 = mcws[u][1];
  }

  for (int k = 0; k < BN - 1; k++)
    for (int u = 0; u < n; u++) {
      int v = ps[u][k];
      if (v >= 0) {
	ps[u][k + 1] = ps[v][k];
	es[u][k + 1] = es[u][k] + es[v][k];
      }
      else
	ps[u][k + 1] = -1;
    }

  int qn;
  scanf("%d", &qn);

  while (qn--) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--, y--;

    ll sum = 0;
    if (ds[x] > ds[y]) swap(x, y);

    Edge ex, ey;
    for (int k = BN - 1; k >= 0; k--)
      if (((ds[y] - ds[x]) >> k) & 1) {
	ey = ey + es[y][k];
	y = ps[y][k];
      }

    if (x == y) {
      int minw = min(ey.mw0, min(getmcw(mcws[y], ey.cw), es[y][0].cw));
      if (minw >= INF) puts("-1");
      else printf("%lld\n", ey.sum + minw * 2);
    }
    else {
      for (int k = BN - 1; k >= 0; k--)
	if (ps[x][k] != ps[y][k]) {
	  ex = ex + es[x][k];
	  ey = ey + es[y][k];
	  x = ps[x][k];
	  y = ps[y][k];
	}

      ex = ex + es[x][0];
      ey = ey + es[y][0];

      int z = ps[x][0];
      int cw0 = ex.cw, cw1 = ey.cw;
      if (cw0 > cw1) swap(cw0, cw1);

      int minw = min(min(ex.mw0, ey.mw0),
		     min(getmcw(mcws[z], cw0, cw1), es[z][0].cw));
      if (minw >= INF) puts("-1");
      else printf("%lld\n", ex.sum + ey.sum + minw * 2);
    }
  }
  return 0;
}
0