QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#692298#5439. Meet in the Middlepeaneval_kalaWA 25ms87292kbC++2310.4kb2024-10-31 14:17:252024-10-31 14:17:31

Judging History

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

  • [2024-10-31 14:17:31]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:87292kb
  • [2024-10-31 14:17:25]
  • 提交

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'