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

提出ソース

結果

問題	No.1212 Second Path
ユーザー	chocorusk
提出日時	2020-08-31 01:22:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	637 ms / 3,000 ms
コード長	5,535 bytes
コンパイル時間	2,181 ms
コンパイル使用メモリ	159,776 KB
実行使用メモリ	78,596 KB
最終ジャッジ日時	2024-04-27 13:53:41
合計ジャッジ時間	26,999 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	419 ms 51,484 KB
testcase_01	AC	526 ms 54,488 KB
testcase_02	AC	614 ms 49,684 KB
testcase_03	AC	509 ms 49,812 KB
testcase_04	AC	534 ms 47,892 KB
testcase_05	AC	510 ms 48,152 KB
testcase_06	AC	629 ms 78,592 KB
testcase_07	AC	637 ms 63,620 KB
testcase_08	AC	619 ms 63,388 KB
testcase_09	AC	633 ms 63,632 KB
testcase_10	AC	635 ms 63,636 KB
testcase_11	AC	613 ms 63,384 KB
testcase_12	AC	616 ms 63,644 KB
testcase_13	AC	606 ms 63,628 KB
testcase_14	AC	623 ms 63,396 KB
testcase_15	AC	619 ms 63,496 KB
testcase_16	AC	614 ms 63,388 KB
testcase_17	AC	401 ms 51,352 KB
testcase_18	AC	185 ms 11,392 KB
testcase_19	AC	187 ms 11,392 KB
testcase_20	AC	179 ms 11,392 KB
testcase_21	AC	185 ms 11,520 KB
testcase_22	AC	180 ms 11,392 KB
testcase_23	AC	170 ms 11,392 KB
testcase_24	AC	167 ms 11,392 KB
testcase_25	AC	167 ms 11,520 KB
testcase_26	AC	175 ms 11,392 KB
testcase_27	AC	167 ms 11,520 KB
testcase_28	AC	168 ms 11,520 KB
testcase_29	AC	455 ms 51,480 KB
testcase_30	AC	460 ms 51,480 KB
testcase_31	AC	452 ms 51,352 KB
testcase_32	AC	502 ms 47,988 KB
testcase_33	AC	438 ms 40,468 KB
testcase_34	AC	602 ms 60,656 KB
testcase_35	AC	264 ms 15,684 KB
testcase_36	AC	498 ms 49,464 KB
testcase_37	AC	488 ms 46,116 KB
testcase_38	AC	502 ms 47,796 KB
testcase_39	AC	395 ms 31,436 KB
testcase_40	AC	215 ms 11,904 KB
testcase_41	AC	504 ms 48,140 KB
testcase_42	AC	6 ms 11,392 KB
testcase_43	AC	6 ms 11,392 KB
testcase_44	AC	6 ms 11,392 KB
testcase_45	AC	609 ms 78,588 KB
testcase_46	AC	609 ms 78,596 KB
testcase_47	AC	612 ms 78,588 KB

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

ソースコード

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];
	multiset<ll> st[100010];
	for(int x=0; x<n; x++){
		for(int i=0; i<g[x].size(); i++){
			if(g[x][i]!=par[x]) st[x].insert(to[x][i]);
		}
	}
	fill(mn, mn+n1, P(INF, INF));
	for(int i=1; i<n1; i++){
		int x=par[i];
		st[x].erase(st[x].lower_bound(wp[i]));
		if(st[x].size()==1){
			mn[i].first=*st[x].begin();
		}else if(st[x].size()){
			auto itr=st[x].begin();
			mn[i].first=*itr;
			itr++;
			mn[i].second=*itr;
		}
		st[x].insert(wp[i]);
	}
	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--;
		printf("%lld\n", solve(x, y));
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード