#544170 (C++11) No.1212 Second Path

提出ソース

結果

問題	No.1212 Second Path
ユーザー	leaf_1415
提出日時	2020-08-30 15:24:41
言語	C++11 (gcc 11.4.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	170 ms 59,604 KB
testcase_01	AC	327 ms 55,168 KB
testcase_02	AC	316 ms 53,888 KB
testcase_03	AC	317 ms 54,016 KB
testcase_04	AC	342 ms 51,072 KB
testcase_05	AC	342 ms 51,200 KB
testcase_06	AC	205 ms 44,516 KB
testcase_07	AC	238 ms 45,184 KB
testcase_08	AC	244 ms 45,312 KB
testcase_09	AC	245 ms 45,312 KB
testcase_10	AC	236 ms 45,312 KB
testcase_11	AC	235 ms 45,312 KB
testcase_12	AC	246 ms 45,184 KB
testcase_13	AC	233 ms 45,312 KB
testcase_14	AC	246 ms 45,184 KB
testcase_15	AC	241 ms 45,312 KB
testcase_16	AC	245 ms 45,184 KB
testcase_17	AC	169 ms 56,192 KB
testcase_18	AC	43 ms 10,496 KB
testcase_19	AC	43 ms 10,496 KB
testcase_20	AC	42 ms 10,368 KB
testcase_21	AC	41 ms 10,496 KB
testcase_22	AC	42 ms 10,496 KB
testcase_23	AC	31 ms 10,496 KB
testcase_24	AC	34 ms 10,368 KB
testcase_25	AC	32 ms 10,240 KB
testcase_26	AC	35 ms 10,368 KB
testcase_27	AC	35 ms 10,496 KB
testcase_28	AC	34 ms 10,368 KB
testcase_29	AC	267 ms 56,192 KB
testcase_30	AC	272 ms 56,192 KB
testcase_31	AC	280 ms 56,192 KB
testcase_32	AC	197 ms 36,224 KB
testcase_33	AC	165 ms 30,336 KB
testcase_34	AC	238 ms 42,880 KB
testcase_35	AC	66 ms 13,440 KB
testcase_36	AC	199 ms 37,376 KB
testcase_37	AC	191 ms 34,816 KB
testcase_38	AC	195 ms 36,096 KB
testcase_39	AC	138 ms 24,576 KB
testcase_40	AC	48 ms 10,624 KB
testcase_41	AC	207 ms 36,224 KB
testcase_42	AC	7 ms 10,368 KB
testcase_43	AC	6 ms 10,368 KB
testcase_44	AC	7 ms 10,368 KB
testcase_45	AC	216 ms 44,644 KB
testcase_46	AC	218 ms 44,516 KB
testcase_47	AC	214 ms 44,644 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード