#544913 (C++17) No.1212 Second Path

提出ソース

結果

問題	No.1212 Second Path
ユーザー	chocorusk
提出日時	2020-08-31 00:51:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,293 bytes
コンパイル時間	2,194 ms
コンパイル使用メモリ	155,284 KB
実行使用メモリ	90,508 KB
最終ジャッジ日時	2024-11-15 16:04:59
合計ジャッジ時間	39,404 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	375 ms 47,124 KB
testcase_01	AC	498 ms 46,484 KB
testcase_02	AC	495 ms 45,716 KB
testcase_03	AC	506 ms 90,508 KB
testcase_04	AC	486 ms 43,668 KB
testcase_05	AC	471 ms 88,856 KB
testcase_06	TLE	-
testcase_07	AC	555 ms 51,720 KB
testcase_08	AC	598 ms 51,740 KB
testcase_09	AC	642 ms 51,724 KB
testcase_10	AC	643 ms 51,596 KB
testcase_11	AC	653 ms 51,732 KB
testcase_12	AC	653 ms 51,740 KB
testcase_13	AC	621 ms 51,728 KB
testcase_14	AC	602 ms 51,876 KB
testcase_15	AC	594 ms 51,592 KB
testcase_16	AC	580 ms 51,740 KB
testcase_17	AC	384 ms 41,752 KB
testcase_18	AC	171 ms 6,656 KB
testcase_19	AC	172 ms 6,656 KB
testcase_20	AC	169 ms 6,656 KB
testcase_21	AC	168 ms 6,656 KB
testcase_22	AC	170 ms 6,656 KB
testcase_23	AC	153 ms 6,656 KB
testcase_24	AC	154 ms 6,784 KB
testcase_25	AC	181 ms 6,656 KB
testcase_26	AC	182 ms 6,656 KB
testcase_27	AC	156 ms 6,656 KB
testcase_28	AC	155 ms 6,656 KB
testcase_29	AC	419 ms 41,748 KB
testcase_30	AC	421 ms 41,876 KB
testcase_31	AC	436 ms 41,876 KB
testcase_32	AC	471 ms 38,132 KB
testcase_33	AC	421 ms 31,768 KB
testcase_34	AC	530 ms 49,264 KB
testcase_35	AC	243 ms 10,180 KB
testcase_36	AC	480 ms 39,348 KB
testcase_37	AC	468 ms 36,516 KB
testcase_38	AC	497 ms 38,064 KB
testcase_39	AC	361 ms 23,756 KB
testcase_40	AC	186 ms 6,912 KB
testcase_41	AC	480 ms 38,024 KB
testcase_42	AC	3 ms 6,784 KB
testcase_43	AC	4 ms 6,656 KB
testcase_44	AC	4 ms 6,656 KB
testcase_45	TLE	-
testcase_46	TLE	-
testcase_47	TLE	-

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

ソースコード

raw source code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<typename Monoid>
struct SegmentTree{
	using F=function<Monoid(Monoid, Monoid)>;
	int sz;
	vector<Monoid> seg;
	const F f;
	const Monoid e;

	SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
	}

	SegmentTree(int n, const F f, const Monoid &e, vector<Monoid> v): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
		for(int i=0; i<n; i++) seg[i+sz]=v[i];
		for(int i=sz-1; i>=1; i--){
			seg[i]=f(seg[2*i], seg[2*i+1]);
		}
	}

	void update(int k, const Monoid &x){
		k+=sz;
		seg[k]=x;
		while(k>1){
			k>>=1;
			seg[k]=f(seg[2*k], seg[2*k+1]);
		}
	}

	Monoid query(int a, int b){
		a+=sz, b+=sz;
		Monoid retl=e, retr=e;
		for(;a<b; a>>=1, b>>=1){
			if(b&1) retr=f(seg[--b], retr);
			if(a&1) retl=f(retl, seg[a++]);
		}
		return f(retl, retr);
	}

	Monoid operator[](const int &k) const{
		return seg[k+sz];
	}
};
struct HeavyLightDecomposition{
	vector<vector<int>> g;
	vector<int> in, out, rev, cnt, head, par;
	HeavyLightDecomposition(const vector<vector<int>> &g):g(g), in(g.size()), out(g.size()), rev(g.size()), cnt(g.size()), head(g.size()), par(g.size()){}
	void dfs(int x, int p){
		cnt[x]=1, par[x]=p;
		int mx=-1, k=-1;
		for(int i=0; i<g[x].size(); i++){
			int y=g[x][i];
			if(y==p) continue;
			dfs(y, x);
			cnt[x]+=cnt[y];
			if(mx<cnt[y]) mx=cnt[y], k=i;
		}
		if(k>0) swap(g[x][k], g[x][0]);
	}
	void dfs2(int x, int p, int &t){
		in[x]=t++;
		rev[in[x]]=x;
		for(int i=0; i<g[x].size(); i++){
			int y=g[x][i];
			if(y==p) continue;
			if(i) head[y]=y;
			else head[y]=head[x];
			dfs2(y, x, t);
		}
		out[x]=t;
	}
	void build(){
		int t=0;
		dfs(0, -1);
		dfs2(0, -1, t);
	}
	int la(int v, int k){
		while(1){
			int u=head[v];
			if(in[v]-k>=in[u]) return rev[in[v]-k];
			k-=in[v]-in[u]+1;
			v=par[u];
		}
	}
	int lca(int u, int v){
		for(; ; v=par[head[v]]){
			if(in[u]>in[v]) swap(u, v);
			if(head[u]==head[v]) return u;
		}
	}
	template<typename F, typename T, typename Q>
	T query(int u, int v, const F &f, const T &e, const Q &q){
		T ret=e;
		for(; ; v=par[head[v]]){
			if(in[u]>in[v]) swap(u, v);
			if(head[u]==head[v]) break;
			ret=f(q(in[head[v]], in[v]+1), ret);
		}
		ret=f(q(in[u], in[v]+1), ret);
		return ret;
	}
};
int main()
{
	int n; cin>>n;
	vector<vector<int>> g(n);
	vector<vector<ll>> to(n);
	for(int i=0; i<n-1; i++){
		int u, v;
		ll w;
		cin>>u>>v>>w;
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
		to[u].push_back(w);
		to[v].push_back(w);
	}
	int n1=n;
	for(int i=1; i<n; i++){
		if(g[i].size()==1){
			n1++;
		}
	}
	const ll INF=1e9+7;
	g.resize(n1);
	to.resize(n1);
	n1=n;
	for(int i=1; i<n; i++){
		if(g[i].size()==1){
			g[i].push_back(n1);
			g[n1].push_back(i);
			to[i].push_back(INF);
			to[n1].push_back(INF);
			n1++;
		}
	}
	auto minp=[](P a, P b){
		if(a.first>b.first) swap(a, b);
		return P(a.first, min(b.first, a.second));
	};
	HeavyLightDecomposition hld(g);
	hld.build();
	ll s[200020], wp[200020];
	int d[200020];
	int par[200020];
	par[0]=-1, s[0]=0, d[0]=0, wp[0]=INF;
	auto dfs=[&](auto dfs, int x, int p)->void{
		for(int i=0; i<g[x].size(); i++){
			int y=g[x][i];
			if(y==p){
				wp[x]=to[x][i];
				par[x]=y;
			}else{
				s[y]=s[x]+to[x][i];
				d[y]=d[x]+1;
				dfs(dfs, y, x);
			}
		}
	};
	dfs(dfs, 0, -1);
	P mn[200020];
	fill(mn, mn+n1, P(INF, INF));
	for(int i=1; i<n1; i++){
		int x=par[i];
		for(int j=0; j<g[x].size(); j++){
			int y=g[x][j];
			if(y==i || y==par[x]) continue;
			mn[i]=minp(mn[i], P(to[x][j], INF));
		}
	}
	vector<P> v(n1);
	for(int i=0; i<n1; i++) v[hld.in[i]]=mn[i];
	SegmentTree<P> seg(n1, minp, P(INF, INF), v);
	auto qr=[&](int l, int r){ return seg.query(l, r);};
	auto solve1=[&](int x, int p, int p1){
		int x1=g[x].back();
		ll w1=to[x].back();
		if(x1==par[x]){
			x1=g[x][0];
			w1=to[x][0];
		}
		return minp(hld.query(x1, p1, minp, P(INF, INF), qr), P(w1, INF));
	};
	auto solve=[&](int x, int y){
		int p=hld.lca(x, y);
		if(p==x){
			int p1=hld.la(y, d[y]-d[p]-1);
			ll myon=min(solve1(y, p, p1).first, wp[p]);
			if(myon==INF) return -1ll;
			else return s[y]-s[p]+2*myon;
		}else if(p==y){
			int p1=hld.la(x, d[x]-d[p]-1);
			ll myon=min(solve1(x, p, p1).first, wp[p]);
			if(myon==INF) return -1ll;
			else return s[x]-s[p]+2*myon;
		}
		int p1=hld.la(x, d[x]-d[p]-1), p2=hld.la(y, d[y]-d[p]-1);
		P mn1=solve1(x, p, p1), mn2=solve1(y, p, p2);
		ll mn0=mn1.first;
		if(mn1.first==wp[p2]) mn0=mn1.second;
		if(mn2.first==wp[p1]) mn0=min(mn0, mn2.second);
		else mn0=min(mn0, mn2.first);
		mn0=min(mn0, wp[p]);
		if(mn0==INF) return -1ll;
		else return s[x]+s[y]-2*s[p]+2*mn0;
	};
	int q; cin>>q;
	while(q--){
		int x, y; cin>>x>>y;
		x--; y--;
		cout<<solve(x, y)<<endl;
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード