QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692267 | #5439. Meet in the Middle | cmk666 | ML | 0ms | 0kb | C++23 | 5.9kb | 2024-10-31 14:14:15 | 2024-10-31 14:14:16 |
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