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

提出ソース

結果

問題	No.1212 Second Path
ユーザー	yosupot
提出日時	2020-08-30 14:33:04
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	713 ms / 3,000 ms
コード長	10,861 bytes
コンパイル時間	1,534 ms
コンパイル使用メモリ	127,712 KB
実行使用メモリ	33,652 KB
最終ジャッジ日時	2023-08-09 12:29:56
合計ジャッジ時間	26,207 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	135 ms 32,600 KB
testcase_01	AC	578 ms 32,684 KB
testcase_02	AC	594 ms 32,796 KB
testcase_03	AC	583 ms 32,728 KB
testcase_04	AC	596 ms 33,036 KB
testcase_05	AC	577 ms 32,708 KB
testcase_06	AC	512 ms 33,192 KB
testcase_07	AC	690 ms 32,724 KB
testcase_08	AC	689 ms 32,796 KB
testcase_09	AC	692 ms 32,652 KB
testcase_10	AC	692 ms 32,676 KB
testcase_11	AC	713 ms 32,668 KB
testcase_12	AC	693 ms 32,820 KB
testcase_13	AC	691 ms 32,672 KB
testcase_14	AC	689 ms 32,788 KB
testcase_15	AC	692 ms 32,676 KB
testcase_16	AC	693 ms 32,880 KB
testcase_17	AC	111 ms 32,924 KB
testcase_18	AC	102 ms 4,380 KB
testcase_19	AC	106 ms 4,380 KB
testcase_20	AC	106 ms 4,380 KB
testcase_21	AC	80 ms 4,376 KB
testcase_22	AC	100 ms 4,376 KB
testcase_23	AC	11 ms 4,380 KB
testcase_24	AC	27 ms 4,380 KB
testcase_25	AC	26 ms 4,380 KB
testcase_26	AC	26 ms 4,376 KB
testcase_27	AC	21 ms 4,380 KB
testcase_28	AC	21 ms 4,376 KB
testcase_29	AC	569 ms 32,792 KB
testcase_30	AC	528 ms 32,784 KB
testcase_31	AC	533 ms 32,668 KB
testcase_32	AC	630 ms 25,080 KB
testcase_33	AC	549 ms 20,172 KB
testcase_34	AC	667 ms 30,756 KB
testcase_35	AC	287 ms 5,640 KB
testcase_36	AC	622 ms 26,040 KB
testcase_37	AC	586 ms 23,832 KB
testcase_38	AC	601 ms 24,916 KB
testcase_39	AC	477 ms 15,364 KB
testcase_40	AC	178 ms 4,376 KB
testcase_41	AC	623 ms 25,112 KB
testcase_42	AC	2 ms 4,380 KB
testcase_43	AC	2 ms 4,376 KB
testcase_44	AC	2 ms 4,376 KB
testcase_45	AC	511 ms 33,652 KB
testcase_46	AC	515 ms 33,264 KB
testcase_47	AC	511 ms 33,328 KB

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

ソースコード

raw source code

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL




#include <algorithm>

#include <array>

#include <bitset>

#include <cassert>

#include <complex>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;



#include <unistd.h>

struct Scanner {
    int fd = -1;
    char line[(1 << 15) + 1];
    size_t st = 0, ed = 0;
    void reread() {
        memmove(line, line + st, ed - st);
        ed -= st;
        st = 0;
        ed += ::read(fd, line + ed, (1 << 15) - ed);
        line[ed] = '\0';
    }
    bool succ() {
        while (true) {
            if (st == ed) {
                reread();
                if (st == ed) return false;
            }
            while (st != ed && isspace(line[st])) st++;
            if (st != ed) break;
        }
        if (ed - st <= 50) {
            bool sep = false;
            for (size_t i = st; i < ed; i++) {
                if (isspace(line[i])) {
                    sep = true;
                    break;
                }
            }
            if (!sep) reread();
        }
        return true;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        while (true) {
            size_t sz = 0;
            while (st + sz < ed && !isspace(line[st + sz])) sz++;
            ref.append(line + st, sz);
            st += sz;
            if (!sz || st != ed) break;
            reread();
        }
        return true;
    }
    template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
    bool read_single(T& ref) {
        if (!succ()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        ref = T(0);
        while (isdigit(line[st])) {
            ref = 10 * ref + (line[st++] & 0xf);
        }
        if (neg) ref = -ref;
        return true;
    }
    template <class T> bool read_single(V<T>& ref) {
        for (auto& d : ref) {
            if (!read_single(d)) return false;
        }
        return true;
    }
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
    int read_unsafe() { return 0; }
    template <class H, class... T> int read_unsafe(H& h, T&... t) {
        bool f = read_single(h);
        if (!f) return 0;
        return 1 + read_unsafe(t...);
    }
    Scanner(FILE* fp) : fd(fileno(fp)) {}
};

struct Printer {
  public:
    template <bool F = false> void write() {}
    template <bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(' ');
        write_single(h);
        write<true>(t...);
    }
    template <class... T> void writeln(const T&... t) {
        write(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fp(_fp) {}
    ~Printer() { flush(); }

  private:
    static constexpr size_t SIZE = 1 << 15;
    FILE* fp;
    char line[SIZE], small[50];
    size_t pos = 0;
    void flush() {
        fwrite(line, 1, pos, fp);
        pos = 0;
    }
    void write_single(const char& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }
    template <class T, enable_if_t<is_integral<T>::value>* = nullptr>
    void write_single(T val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val; // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char(0x30 | (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }
    void write_single(__int128 val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val; // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char(0x30 | (val % 10));
            val /= 10;
        }
        for (size_t i = 0; i < len; i++) {
            line[pos + i] = small[len - 1 - i];
        }
        pos += len;
    }

    void write_single(const string& s) {
        for (char c : s) write_single(c);
    }
    void write_single(const char* s) {
        size_t len = strlen(s);
        for (size_t i = 0; i < len; i++) write_single(s[i]);
    }
    template <class T> void write_single(const V<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
};

Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);

struct TTNode {
    using NP = TTNode*;

    bool rev = false;
    array<array<NP, 2>, 2> ch = {}; // tree, light-tree
    NP p = nullptr, lt = nullptr;

    struct D {
        ll top = TEN(18), last = TEN(18), all_min = TEN(18), dist = 0;
        // l is parent of r
        static D merge_h(const D& l, const D& r) {
            return {l.top, r.last, min(l.all_min, r.all_min), l.dist + r.dist};
        }
        // l and r is parallel
        static D merge_w(const D& l, const D& r) {
            return {min(l.top, r.top), -1, -1, -1};
        }
        // add parent for r(subtrees)
        static D join(const D& l, const D& r) {
            return {l.top, l.last, min(l.all_min, r.top), l.dist};
        }
        D rev() { return D{last, top, all_min, dist}; }
        D to_subs() { return D{top, -1, -1, -1}; }
    };
    D single = D(), sub = D(), subs = D();

    void init_node(ll x) {
        single = D{x, x, TEN(18), x == TEN(18) ? 0 : x};
        update();
    }
    void update_subs() {
        subs = sub.to_subs();
        if (ch[1][0]) subs = D::merge_w(ch[1][0]->subs, subs);
        if (ch[1][1]) subs = D::merge_w(subs, ch[1][1]->subs);
    }
    void update() {
        assert(!rev);
        sub = single;
        if (lt) sub = D::join(single, lt->subs);
        if (ch[0][0]) sub = D::merge_h(ch[0][0]->sub, sub);
        if (ch[0][1]) sub = D::merge_h(sub, ch[0][1]->sub);
        update_subs();
    }
    void revdata() {
        rev ^= true;
        swap(ch[0][0], ch[0][1]); // Important
        sub = sub.rev();
        update_subs();
    }
    void push() {
        if (rev) {
            if (ch[0][0]) ch[0][0]->revdata();
            if (ch[0][1]) ch[0][1]->revdata();
            rev = false;
        }
    }
    // optimize? : template<int ty>
    int pos(int ty) {
        if (p) {
            if (p->ch[ty][0] == this) return 0;
            if (p->ch[ty][1] == this) return 1;
        }
        return -1;
    }
    static void con(NP p, NP& cp, NP ch) {
        cp = ch;
        if (ch) ch->p = p;
    }
    void rot(int ty) {
        int ps = pos(ty);
        NP _p = p, q = p->p;
        if (ty == 0) {
            ch[1] = _p->ch[1];
            _p->ch[1].fill(nullptr);
            for (auto& x : ch[1])
                if (x) x->p = this;
        }
        con(_p, _p->ch[ty][ps], ch[ty][1 - ps]);
        con(this, ch[ty][1 - ps], _p);
        _p->update();
        update();
        p = q;
        if (!q) return;
        if (q->lt == _p) q->lt = this;
        for (auto& v : q->ch)
            for (auto& x : v)
                if (x == _p) x = this;
        q->update();
    }
    void splay(int ty) {
        int ps;
        while ((ps = pos(ty)) != -1) {
            int pps = p->pos(ty);
            if (pps == -1) {
                rot(ty);
            } else if (ps == pps) {
                p->rot(ty);
                rot(ty);
            } else {
                rot(ty);
                rot(ty);
            }
        }
    }
    void expose() {
        supush();
        splay(0);
        splay(1);
        if (NP z = ch[0][1]) {
            z->push();
            con(z, z->ch[1][1], lt);
            lt = z;
            ch[0][1] = nullptr;
            z->update();
            update();
        }
        NP u = p;
        while (u) {
            u->splay(0);
            u->splay(1);
            NP ur = u->lt;
            if (auto r = u->ch[0][1]) {
                // swap ur, r
                r->push();
                r->ch[1] = ur->ch[1];
                ur->ch[1].fill(nullptr);
                for (auto& x : r->ch[1])
                    if (x) x->p = r;
                r->update();
                u->lt = r;
            } else if (!ur->ch[1][0]) {
                // use ur->ch[1][1]
                con(u, u->lt, ur->ch[1][1]);
            } else {
                // use prev(ur) in light-tree
                NP q = ur->ch[1][0];
                con(u, u->lt, q);
                q->push();
                while (q->ch[1][1]) {
                    q = q->ch[1][1];
                    q->push();
                }
                q->splay(1);
                con(q, q->ch[1][1], ur->ch[1][1]);
                q->update();
            }
            ur->ch[1].fill(nullptr);
            ur->update();
            u->ch[0][1] = ur;
            u->update();
            u = u->p;
        }
        splay(0);
    }
    void supush() {
        if (p) p->supush();
        push();
    }
    void link(NP r) {
        evert();
        r->expose();
        assert(!r->ch[0][1]);
        con(r, r->ch[0][1], this);
        r->update();
    }
    void cut() {
        expose();
        assert(ch[0][0]);
        ch[0][0]->p = nullptr;
        ch[0][0] = nullptr;
        update();
    }
    void evert() {
        expose();
        revdata();
        expose();
    }
};

int main() {
    int n;
    sc.read(n);
    V<TTNode> node(2 * n - 1);
    for (int i = 0; i < n; i++) {
        node[i].init_node(TEN(18));
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v; ll w;
        sc.read(u, v, w); u--; v--;
        node[n + i].init_node(w);
        node[u].link(&(node[n + i]));
        node[n + i].link(&(node[v]));
    }

    int q;
    sc.read(q);
    for (int i = 0; i < q; i++) {
        int u, v;
        sc.read(u, v); u--; v--;
        node[u].evert();
        node[v].expose();
        auto x = node[v].sub;
                              ;
        if (x.all_min == TEN(18)) {
            pr.writeln(-1);
        } else {
            pr.writeln(x.all_min * 2 + x.dist);
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード