結果

問題 No.1212 Second Path
ユーザー leaf_1415
提出日時 2020-08-30 15:24:41
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 342 ms / 3,000 ms
コード長 3,801 bytes
コンパイル時間 1,642 ms
コンパイル使用メモリ 92,424 KB
実行使用メモリ 59,604 KB
最終ジャッジ日時 2024-11-15 08:55:44
合計ジャッジ時間 14,662 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 1000000007
using namespace std;
typedef pair<llint, llint> P;
struct edge{
llint to, cost;
edge(){}
edge(llint a, llint b){
to = a, cost = b;
}
};
llint n, Q;
vector<edge> G[100005];
set<P> S[100005];
int Prev[200005][18];
llint depth[200005], dist[200005], pcost[200005];
llint mini[200005][18];
int getLCA(int u, int v){
int x = u, y = v;
if(depth[y] > depth[x]) swap(x, y);
for(int i = 17; i >= 0; i--){
if(depth[x] - (1<<i) >= depth[y]) x = Prev[x][i];
}
if(x == y) return x;
for(int i = 17; i >= 0; i--){
if(Prev[x][i] != Prev[y][i]){
x = Prev[x][i];
y = Prev[y][i];
}
}
x = Prev[x][0];
return x;
}
void predfs(int v, int p, int d, llint s, llint pc)
{
depth[v] = d, dist[v] = s, Prev[v][0] = p, pcost[v] = pc;
for(int i = 0; i < G[v].size(); i++){
if(G[v][i].to == p) continue;
predfs(G[v][i].to, v, d+1, s + G[v][i].cost, G[v][i].cost);
S[v].insert(P(G[v][i].cost, G[v][i].to));
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
llint u, v, w;
for(int i = 1; i <= n-1; i++){
cin >> u >> v >> w;
G[u].push_back(edge(v, w));
G[v].push_back(edge(u, w));
}
predfs(1, 0, 0, 0, inf);
for(int i = 1; i < 18; i++){
for(int j = 1; j <= n; j++){
Prev[j][i] = Prev[Prev[j][i-1]][i-1];
}
}
for(int i = 1; i <= n; i++){
llint p = Prev[i][0]; mini[i][0] = inf;
if(p == 0) continue;
for(auto it = S[p].begin(); it != S[p].end(); it++){
if(it->second != i){
mini[i][0] = it->first;
break;
}
}
}
for(int i = 1; i < 18; i++){
for(int j = 1; j <= n; j++){
mini[j][i] = mini[j][i-1];
if(Prev[j][i-1]) chmin(mini[j][i], mini[Prev[j][i-1]][i-1]);
}
}
/*for(int i = 0; i < 18; i++){
for(int j = 1; j <= n; j++){
cout << mini[j][i] << " ";
}
cout << endl;
}*/
cin >> Q;
llint x, y;
for(int q = 0; q < Q; q++){
cin >> x >> y;
llint lca = getLCA(x, y), mn = inf, ans = dist[x]+dist[y]-2*dist[lca];
//cout << "Q " << x << " " << y << endl;
//cout << lca << " " << ans << endl;
if(lca != x && lca != y){
if(S[x].size()) mn = min(mn, S[x].begin()->first);
if(S[y].size()) mn = min(mn, S[y].begin()->first);
llint rem = depth[x] - depth[lca] - 1, v = x, w = y;
for(int i = 17; i >= 0; i--){
if(rem & (1<<i)){
mn = min(mn, mini[v][i]);
v = Prev[v][i];
}
}
rem = depth[y] - depth[lca] - 1;
for(int i = 17; i >= 0; i--){
if(rem & (1<<i)){
mn = min(mn, mini[w][i]);
w = Prev[w][i];
}
}
//cout << u << " " << v << endl;
for(auto it = S[lca].begin(); it != S[lca].end(); it++){
if(it->second != v && it->second != w){
mn = min(mn, it->first);
break;
}
}
mn = min(mn, pcost[lca]);
}
else{
if(lca == y) swap(x, y);
if(S[y].size()) mn = min(mn, S[y].begin()->first);
llint rem = depth[y] - depth[lca] - 1, w = y;
for(int i = 17; i >= 0; i--){
if(rem & (1<<i)){
mn = min(mn, mini[w][i]);
w = Prev[w][i];
}
}
for(auto it = S[x].begin(); it != S[x].end(); it++){
if(it->second != w){
mn = min(mn, it->first);
break;
}
}
mn = min(mn, pcost[lca]);
}
if(mn > inf/2) cout << -1 << "\n";
else{
ans += mn*2;
cout << ans << "\n";
}
}
flush(cout);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0