QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692267#5439. Meet in the Middlecmk666ML 0ms0kbC++235.9kb2024-10-31 14:14:152024-10-31 14:14:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 14:14:16]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-31 14:14:15]
  • 提交

answer

#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
	constexpr int N = 1 << 18; char i[N], *ip = i, *iq = i, o[N], *op = o;
	inline char gc() { return ip == iq ? ( iq = i + fread(ip = i, 1, N, stdin), ip == iq ? EOF : *ip++ ) : *ip++; }
	inline void flush() { fwrite(o, 1, op - o, stdout), op = o; }
	inline void pc(char c) { *op++ = c; if ( op == o + N ) flush(); }
	template < class T > inline void read(T &x) { char c = gc(); while ( !isdigit(c) ) c = gc(); x = 0; while ( isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc(); }
	template < class T > inline void write(T x) { char b[numeric_limits < T >::digits10]; int d = 0; do b[d++] = ( x % 10 ) | 48, x /= 10; while ( x ); while ( d ) pc(b[--d]); }
}
template < class T, int N, int M > class darry
{
	inline constexpr static int calc(int x) { return ( __lg(x) + 2 ) >> 1; }
	T a[M]; int b[N], c[1 << calc(N)], n, m, o;
	struct E { int u; T v; } e[M], f[M];
	class V { T *b, *e; public: explicit inline V(T *b, T *e) : b(b), e(e) {} inline T *begin()const { return b; } inline T *end()const { return e; } inline auto size()const { return e - b; } };
public:
	inline void init(int n_) { n = n_, m = 0, o = calc(n), fill(b + 1, b + n + 1, 0); }
	template < class ...U > inline void emplace(int u, U&& ...v) { b[u]++, e[++m] = E{u, T(forward<U>(v)...)}; }
	inline void build() { fill(c, c + ( 1 << o ), 0); For(i, 1, m) c[e[i].u & ( ( 1 << o ) - 1 )]++; For(i, 1, ( 1 << o ) - 1) c[i] += c[i - 1]; Fol(i, m, 1) f[c[e[i].u & ( ( 1 << o ) - 1 )]--] = move(e[i]); fill(c, c + ( 1 << o ), 0); For(i, 1, m) c[f[i].u >> o]++; For(i, 1, ( 1 << o ) - 1) c[i] += c[i - 1]; Fol(i, m, 1) a[c[f[i].u >> o]--] = move(f[i].v); *b = 1; For(i, 1, n) b[i] += b[i - 1]; }
	inline V operator[](int u) { return V(a + b[u - 1], a + b[u]); }
};
int n, o, q, u, v, w, dfn[100009], cnt, st[17][100009], sz[200009], p[4][200009], pl[4], tot;
ll dep1[200009], dep2[100009], ans[500009]; bool used[200009]; tuple < ll, int, int > bst[4], cur;
darry < pair < int, int >, 100009, 200009 > g1, g2;
darry < pair < int, int >, 200009, 400009 > g; darry < pair < int, int >, 100009, 500009 > qry;
inline void dfs1(int u, int fa = 0)
{
	int nw = 0;
	for ( auto _ : g1[u] ) if ( _.first != fa )
	{
		if ( !nw ) nw = u; else g.emplace(nw, ++o, 0), g.emplace(o, nw, 0), nw = o;
		g.emplace(nw, _.first, _.second), g.emplace(_.first, nw, _.second), dfs1(_.first, u);
	}
}
inline void dfs2(int u, int fa = 0, int fw = 0)
{
	dep2[u] = dep2[fa] + fw, dfn[u] = ++cnt, st[0][dfn[u]] = fa;
	for ( auto _ : g2[u] ) if ( _.first != fa ) dfs2(_.first, u, _.second);
}
inline int cmp(int u, int v) { return dfn[u] < dfn[v] ? u : v; }
inline int lca(int u, int v)
{
	if ( u == v ) return u;
	if ( ( u = dfn[u] ) > ( v = dfn[v] ) ) swap(u, v);
	int t = __lg(v - u++); return cmp(st[t][u], st[t][v + 1 - ( 1 << t )]);
}
inline ll dis(int u, int v) { return dep2[u] + dep2[v] - dep2[lca(u, v)] * 2; }
inline ll calc(int u, int v) { return dis(u, v) + dep1[u] + dep1[v]; }
inline void ins(tuple < ll, int, int > &f, int u)
{
	if ( !get<1>(f) ) { get<1>(f) = u; return; }
	if ( !get<2>(f) ) { get<0>(f) = calc(get<1>(f), get<2>(f) = u); return; }
	ll du = calc(get<1>(f), u), dv = calc(get<2>(f), u);
	if ( du > get<0>(f) && du >= dv ) get<0>(f) = du, get<2>(f) = u;
	if ( dv > get<0>(f) && dv >  du ) get<0>(f) = dv, get<1>(f) = u;
}
inline void slv(int u, int al = o)
{
	int mn = al + 1, rt;
	const auto get_rt = [&](auto &&self, int u, int fa = 0) -> void {
		int mx = 0; sz[u] = 1;
		for ( auto _ : g[u] ) if ( _.first != fa && !used[_.first] )
			self(self, _.first, u), sz[u] += sz[_.first], mx = max(mx, sz[_.first]);
		if ( ( mx = max(mx, al - sz[u]) ) < mn ) mn = mx, rt = u;
	};
	get_rt(get_rt, u), used[rt] = true, assert((int)g[rt].size() < 4);
	dep1[rt] = tot = pl[0] = 0, bst[0] = make_tuple(0, 0, 0);
	if ( rt <= n ) p[0][++pl[0]] = rt, bst[0] = make_tuple(0, rt, 0);
	const auto dfs = [&](auto &&self, int u, int fa, int fw) -> void {
		dep1[u] = dep1[fa] + fw;
		if ( u <= n ) p[tot][++pl[tot]] = u, ins(bst[tot], u);
		for ( auto _ : g[u] ) if ( _.first != fa && !used[_.first] ) self(self, _.first, u, _.second);
	};
	for ( auto _ : g[rt] ) if ( !used[_.first] )
		pl[++tot] = 0, bst[tot] = make_tuple(0, 0, 0), dfs(dfs, _.first, rt, _.second);
	For(i, 0, tot) if ( pl[i] )
	{
		cur = make_tuple(0, 0, 0);
		For(j, 0, tot) if ( i != j )
		{
			if ( get<1>(bst[j]) ) ins(cur, get<1>(bst[j]));
			if ( get<2>(bst[j]) ) ins(cur, get<2>(bst[j]));
		}
		For(j, 1, pl[i]) for ( auto _ : qry[p[i][j]] )
		{
			if ( get<1>(cur) ) ans[_.second] = max(ans[_.second],
				dep1[p[i][j]] + dep1[get<1>(cur)] + dis(_.first, get<1>(cur)));
			if ( get<2>(cur) ) ans[_.second] = max(ans[_.second],
				dep1[p[i][j]] + dep1[get<2>(cur)] + dis(_.first, get<2>(cur)));
		}
	}
	for ( auto _ : g[rt] ) if ( !used[_.first] ) slv(_.first, sz[_.first]);
}
inline void work()
{
	FastIO::read(n), g1.init(n), g2.init(n), g.init(n + n), qry.init(n);
	For(i, 2, n) FastIO::read(u), FastIO::read(v), FastIO::read(w),
				 g1.emplace(u, v, w), g1.emplace(v, u, w);
	For(i, 2, n) FastIO::read(u), FastIO::read(v), FastIO::read(w),
				 g2.emplace(u, v, w), g2.emplace(v, u, w);
	FastIO::read(q), g1.build(), g2.build(), o = n, dfs1(1), g.build(), cnt = 0, dfs2(1);
	For(i, 1, 16) For(j, 1, n + 1 - ( 1 << i ))
		st[i][j] = cmp(st[i - 1][j], st[i - 1][j + ( 1 << ( i - 1 ) )]);
	For(i, 1, q) FastIO::read(u), FastIO::read(v), qry.emplace(u, v, i);
	qry.build(), fill(used + 1, used + o + 1, false), fill(ans + 1, ans + q + 1, 0), slv(1);
	For(i, 1, q) FastIO::write(ans[i]), FastIO::pc('\n');
}
int main()
{
	// freopen("move.in", "r", stdin), freopen("move.out", "w", stdout);
	/*int t; FastIO::read(t); while ( t-- ) */work(); return FastIO::flush(), 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:


result: