QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#692298 | #5439. Meet in the Middle | peaneval_kala | WA | 25ms | 87292kb | C++23 | 10.4kb | 2024-10-31 14:17:25 | 2024-10-31 14:17:31 |
Judging History
answer
#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) { x = min(x, y); }
template <typename T>
inline void chkmax(T &x, T y) { x = max(x, y); }
namespace FastIO
{
// ------------------------------
#define IN_HAS_NEG
#define OUT_HAS_NEG
#define CHK_EOF
#define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined (_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer;
_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
}
return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
{
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
_write_ptr = _write_buffer;
}
}
INLINE_V struct _auto_flush
{
~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline bool _isdigit(char c) { return c & 16; }
inline bool _isgraph(char c) { return c > 32; }
#endif
template < class T >
INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
template < class T >
INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T >
INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) *s++ = c, c = gc();
*s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
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();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T >
static inline void _read(tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T >
static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
};
template < class ...T >
inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T >
inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 >
inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 >
inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 >
inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T >
inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 >
inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T >
inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T >
inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 >
inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template < class ...T >
inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template < class ...T >
inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T >
inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
T y;
swap(x, y);
}
const int N = 1e6 + 10;
struct Tree {
vector<pair<int, int> > vec[N];
ll dis[N];
int fa[N], id[N], dfn[N], dfncnt, siz[N];
ll faw[N];
void dfs(int u) {
siz[u] = 1;
dfn[u] = ++dfncnt, id[dfncnt] = u;
for (auto [v, w] : vec[u]) {
vec[v].erase(find(vec[v].begin(),vec[v].end(), make_pair(u, w)));
fa[v] = u, faw[v] = w, dfs(v);
siz[u] += siz[v];
}
}
void dfs2(int u) {
for (int i = dfn[u] + 1; i < dfn[u] + siz[u]; i++) dis[id[i]] = dis[fa[id[i]]] + faw[id[i]];
}
inline void calcdis(int u) {
dis[u] = 0, dfs2(u);
int pu = 0;
// cerr << "find u,:" << u << endl;
while (fa[u]) {
dis[fa[u]] = dis[u] + faw[u];
pu = u, u = fa[u];
for (int i = dfn[u] + 1; i < dfn[pu]; i++) dis[id[i]] = dis[fa[id[i]]] + faw[id[i]];
for (int i = dfn[pu] + siz[pu]; i < dfn[u] + siz[u]; i++) dis[id[i]] = dis[fa[id[i]]] + faw[id[i]];
}
}
} t1, t2;
int n, m, qu[N], qv[N], fl[N];
vector<int> res;
mt19937_64 rng(random_device{}());
int cT;
ll ans[N];
inline void work() {
clear(res);
t1.dfncnt = t2.dfncnt = 0;
read(n);
read(m);
for (int i = 1; i <= n; i++) clear(t1.vec[i]), clear(t2.vec[i]);
for (int i = 1; i < n; i++) {
int u, v, w;
read(u, v, w), t1.vec[u].push_back(make_pair(v, w)), t1.vec[v].push_back(make_pair(u, w));
}
for (int i = 1; i < n; i++) {
int u, v, w;
read(u, v, w), t2.vec[u].push_back(make_pair(v, w)), t2.vec[v].push_back(make_pair(u, w));
}
for (int i = 1; i <= m; i++) fl[i] = 0;
for (int i = 1; i <= 300; i++) fl[i] = 1;
shuffle(fl + 1, fl + m + 1, rng);
for (int i = 1; i <= m; i++) read(qu[i], qv[i]);
// if (cT == 2) return;
t1.dfs(1), t2.dfs(1);
for (int i = 1; i <= m; i++)
if (fl[i]) {
t1.calcdis(qu[i]), t2.calcdis(qv[i]);
ll ans = -1;
int pos = -1;
for (int j = 1; j <= n; j++) if (ans < t1.dis[j] + t2.dis[j]) pos = j, ans = t1.dis[j] + t2.dis[j];
// cerr << "find i, pos:" << i << ' ' << pos << ' ' << ans << endl;
res.push_back(pos);
}
for (int i = 1; i <= m; i++) ans[i] = -1;
sort(res.begin(), res.end()), res.erase(unique(res.begin(), res.end()), res.end());
// cerr << "find siz:" << res.size() << endl;
for (int v : res) {
// cerr << "find v:" << v << endl;
t1.calcdis(v), t2.calcdis(v);
for (int i = 1; i <= m; i++) chkmax(ans[i], t1.dis[qu[i]] + t2.dis[qv[i]]); // cerr << "find, v:" << t1.dis[qu[i]] << ' ' << t2.dis[qv[i]];
}
for (int i = 1; i <= m; i++) println(ans[i]);
}
int main() {
work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 79424kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
6 4 5 3
result:
ok 4 number(s): "6 4 5 3"
Test #2:
score: 0
Accepted
time: 3ms
memory: 81468kb
input:
2 1 1 2 1 1 2 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 3ms
memory: 81456kb
input:
2 1 1 2 1 1 2 1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 25ms
memory: 85032kb
input:
10000 50000 8101 5996 108427744 5996 7605 870838849 5996 5599 603303696 8101 3006 339377417 8101 6463 442516687 6463 5560 109174079 5560 4063 127596224 3006 1682 947915262 5996 1986 130416311 6463 5455 279771516 6463 2634 516688796 4063 3034 217886863 7605 5092 742375061 5599 2266 193804402 5092 140...
output:
647838384844 626539793176 514273941704 637066393138 472546379596 645842915960 641537859258 573604504956 644081575470 803875451466 674370549986 734764046916 744862815441 763778393516 553499885160 526743824759 610373719514 689550247042 549161302822 726811438160 653134244120 666761991962 701575393972 6...
result:
ok 50000 numbers
Test #5:
score: 0
Accepted
time: 16ms
memory: 85044kb
input:
10000 50000 5314 8843 137901358 5314 4153 459134340 5314 8667 933926892 4153 6504 330487798 4153 8880 750362377 4153 5990 874275912 4153 546 563436331 5990 6216 902348875 8843 3101 669215553 6216 8138 732343176 8667 8675 581114294 6504 7416 127778711 546 4239 282695908 6504 9455 549237168 5314 8340 ...
output:
464564968641 331633000004 565299667784 484694871646 570451097836 417492802442 372302349684 638725688107 386235986078 355738655551 462027769535 558485994764 524714144289 450157947013 432701214095 494566741391 529031758638 637683369382 415646847933 344894296260 390294136162 527685175763 575151290175 3...
result:
ok 50000 numbers
Test #6:
score: 0
Accepted
time: 19ms
memory: 87292kb
input:
10000 50000 2808 2490 757309564 2808 9601 312271047 2808 4046 119325897 2808 4894 466822371 4894 1507 498399554 2490 5982 84088145 9601 1251 149019541 2808 6681 416590999 2808 6583 357757899 1251 3192 889947539 6583 9762 350572496 6681 22 597479070 5982 8744 263208242 8744 5281 49894126 1507 8806 30...
output:
1501072697023 2058806276380 2017086500812 2044250452467 1543567245539 1695101693278 1765462307870 2576423082091 2302805133490 2090282734929 2375783476943 1954788661090 2056530503168 2453153202726 1978028047409 2106220371212 2210163378358 2015714406862 1555876274751 2122832986951 2102262624814 169085...
result:
ok 50000 numbers
Test #7:
score: 0
Accepted
time: 22ms
memory: 83268kb
input:
10000 50000 4064 7188 81750473 7188 8466 310631946 8466 2276 154981798 2276 7347 162965456 7188 464 806245243 464 2250 849189978 8466 641 734602751 8466 9246 225800419 4064 5267 191524437 2276 5292 192776095 2276 9036 414997994 9246 5470 362146726 2250 473 98496385 4064 7726 700294189 473 9503 42824...
output:
3589143478793 5241855728342 3397106617685 3432843859461 4544481241003 3649934075137 3020107625030 3297847713344 3894730366667 3030559097282 4824131552194 4821302024170 4471510161493 3291683748595 4954639576578 2961243269520 3659899432127 3421183608349 5262802614761 4408705330639 5203984107670 500158...
result:
ok 50000 numbers
Test #8:
score: -100
Wrong Answer
time: 24ms
memory: 85192kb
input:
10000 50000 8676 4714 406191383 8676 5040 603960140 5040 9715 635348098 4714 9483 594267326 9483 5451 409058229 8676 8913 909259106 9715 1399 320185961 9715 4857 180234031 4714 8888 585099487 5040 1244 645347755 5451 7736 479423492 9483 1038 272038574 1399 3970 638817231 8888 3314 55726955 8888 2295...
output:
447424387353 491327570749 614052040822 384218910068 429859933145 356174725430 609432604118 465420084327 472632020898 382647454960 343751681021 441874503695 463199624732 610943875286 563031986601 566780763247 346991783125 601234775562 619765985074 357316826763 495874578271 526431260851 331681020073 4...
result:
wrong answer 550th numbers differ - expected: '535172937869', found: '533899228664'